Mathematical Analysis
Solve exactly an under determined linear system by minimizing least squares regularized with an $ℓ0$ penalty
Comptes Rendus. Mathématique, Volume 349 (2011) no. 21-22, pp. 1145-1150.

We analyze objectives $Fd$ combining a quadratic data-fidelity and a weighted $ℓ0$ penalty. Data d are generated using a full column rank $M×N$ matrix A with $N>M$. We provide a detailed analysis of the minimization problem. We exhibit a criterion enabling to recover exactly an original vector $u¨$ with support shorter than $M−1$ as a strict (local) minimizer of $Fd$ where $d=Au¨$.

Nous analysons des objectifs $Fd$ combinant une fidélité aux données quadratique et une pénalisation $ℓ0$. Les données d sont générées par une matrice A de dimension $M×N$ et de rang M$N>M$. Nous donnons une analyse détaillée du problème de minimisation. Nous établissons un critère permettant de retrouver un vecteur original $u¨$ dont la longueur du support ne dépasse pas $M−1$ comme un minimiseur (local) strict de $Fd$$d=Au¨$.

Accepted:
Published online:
DOI: 10.1016/j.crma.2011.08.011

Mila Nikolova 1

1 CMLA, ENS Cachan, CNRS, UniverSud, 61, avenue President Wilson, 94230 Cachan, France
@article{CRMATH_2011__349_21-22_1145_0,
author = {Mila Nikolova},
title = {Solve exactly an under determined linear system by minimizing least squares regularized with an ${\ell }_{0}$ penalty},
journal = {Comptes Rendus. Math\'ematique},
pages = {1145--1150},
publisher = {Elsevier},
volume = {349},
number = {21-22},
year = {2011},
doi = {10.1016/j.crma.2011.08.011},
language = {en},
}
TY  - JOUR
AU  - Mila Nikolova
TI  - Solve exactly an under determined linear system by minimizing least squares regularized with an ${\ell }_{0}$ penalty
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 1145
EP  - 1150
VL  - 349
IS  - 21-22
PB  - Elsevier
DO  - 10.1016/j.crma.2011.08.011
LA  - en
ID  - CRMATH_2011__349_21-22_1145_0
ER  - 
%0 Journal Article
%A Mila Nikolova
%T Solve exactly an under determined linear system by minimizing least squares regularized with an ${\ell }_{0}$ penalty
%J Comptes Rendus. Mathématique
%D 2011
%P 1145-1150
%V 349
%N 21-22
%I Elsevier
%R 10.1016/j.crma.2011.08.011
%G en
%F CRMATH_2011__349_21-22_1145_0
Mila Nikolova. Solve exactly an under determined linear system by minimizing least squares regularized with an ${\ell }_{0}$ penalty. Comptes Rendus. Mathématique, Volume 349 (2011) no. 21-22, pp. 1145-1150. doi : 10.1016/j.crma.2011.08.011. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.08.011/

[1] T. Blumensath; M. Davies Iterative thresholding for sparse approximations, Journal of Fourier Analysis and Applications, Volume 14 (2008) no. 4–6, pp. 629-654

[2] A.M. Bruckstein; D.L. Donoho; M. Elad From sparse solutions of systems of equations to sparse modeling of signals and images, SIAM Review, Volume 51 (2009) no. 1, pp. 34-81

[3] G. Davis; S. Mallat; M. Avellaneda Adaptive greedy approximations, Constructive Approximation, Volume 13 (1997) no. 1, pp. 57-98

[4] D.L. Donoho; I.M. Johnstone Ideal spatial adaptation by wavelet shrinkage, Biometrika, Volume 81 (1994) no. 3, pp. 425-455

[5] G. Gasso; A. Rakotomamonjy; S. Canu Recovering sparse signals with a certain family of non-convex penalties and DC programming, IEEE Transactions on Signal Processing, Volume 57 (2009) no. 12, pp. 4686-4698

[6] J. Haupt; R. Nowak Signal reconstruction from noisy random projections, IEEE Transactions on Information Theory, Volume 52 (2006) no. 9, pp. 4036-4048

[7] Y. Liu; Y. Wu Variable selection via a combination of the $ℓ0$ and $ℓ1$ penalties, Journal of Computational and Graphical Statistics, Volume 16 (2007) no. 4, pp. 782-798

[8] J. Lv; Y. Fan A unified approach to model selection and sparse recovery using regularized least squares, The Annals of Statistics, Volume 37 (2009) no. 6A

[9] S. Mallat A Wavelet Tour of Signal Processing (The Sparse Way), Academic Press, London, 2008

[10] A.J. Miller Subset Selection in Regression, Chapman and Hall, London, UK, 2002

[11] M. Nikolova, On the minimizers of least squares regularized with $ℓ0$ norm, Technical report, 2011.

[12] J. Neumann; C. Schörr; G. Steidl Combined SVM-based feature selection and classification, Machine Learning, Volume 61 (2005), pp. 129-150

[13] J.A. Tropp Just relax: convex programming methods for identifying sparse signals in noise, IEEE Transactions on Information Theory, Volume 52 (2006) no. 3, pp. 1030-1051

Cited by Sources: