Sparsest solutions of underdetermined linear systems via \( \ell _q\)-minimization for \(0<q\leqslant 1\) (Q1012556): Difference between revisions

The paper of Simon Foucart and Ming-Jun Lai is located in the interface between applied linear algebra, the theory of inverse problems and optimization theory. In fact, many real-world problems or discretized versions of continuous problems (of integral equation form) ask for an approximate solution of a linear system of equations, often with ``the'' solution underdetermined. They may have a motivation from data mining, statistics, science or engineering. While the classical goal consists in a highest accuracy of the solution, the often ill-conditionedness (or ill-posedness) of the problem is related with a high sensitivity (or instability, complexity) of the solution and with its selection; both targets constitute a tradeoff. For these reasons, regularization (e.g., Tikhonov regularization) became introduced to diminish the complexity and, herewith, stabilize (regularize) the solution, basically, by making the solution ``small'' - in the sense of its norm or the norm of a ``differentiated'' solution (first-, second-order dervivatives, etc.) small. This paper can, e.g., be regarded in this framework of tradeoff between accuracy and stability, and it involves various concepts of smallness (or size) of the solution, geometric ones and, in particular, ones with a numerical-computational or statistical meaning as well, related with entries (``features'') vanishing (sparsity). So, this paper is about the study of a constrained minimization problem of some norm(s) of the unknown state variable subject to a system of linear equations or, approximately, to inequality constraint(s) on such system(s) under error tolerance(s). This study covers theory, methods, and comparative examples. In the paper, the authors present a condition on the matrix of an underdetermined linear system which guarantees that the solution of the system with mininal \(\ell_q\)-quasinorm is also the sparsest one. This generalizes, and slightly improves, a similar result for the \(\ell_1\)-norm. Then, the authors introduce a simple numerical scheme to compute solutions with minimal \(\ell_q\)-quasinorm, and they study its convergence. Finally, they display the result of some experiments which indicate that the \(\ell_q\)-method performs better than other available methods. This articles is well-structured with five sections, namely, on \textit{introduction, exact recovery via \(\ell_q\)-minimization, approximate recovery from imperfect data, description of the algorithm, and numerical experiments} with its plots on frequency of success vs. number of iternations \(n\), frequency of success vs. exponent \(q\), and frequency of success vs. sparsity s, and comparison of the five algorithms for sparse vectors with arbitrary entries. Namely, these algorithms are the procedure introduced, indeed being competitive, and orthogonal greedy algorithm, regularized orthogonal matching pursuit, \(\ell_1\)-minimization and reweighted \(\ell_1\)-minimization. In fact, as indicated in this report, real-world challenges of various kinds and backgrounds, from financial mathematics and risk-management, Operations Research, natural sciences, engineering and hightech, may in future benefit from the clear, well written and demonstrated contribution and from its solution methods proposed.