Solve exactly an under determined linear system by minimizing least squares regularized with an $ {\ell }_{0}$ penalty

Nikolova, Mila

doi:10.1016/j.crma.2011.08.011

Mathematical Analysis

Solve exactly an under determined linear system by minimizing least squares regularized with an

ℓ_{0}

penalty
[Résoudre exactement un système sous-déterminé en minimisant des moindres carrés régularisés avec

ℓ_{0}

]

Présenté par : Yves Meyer

Nikolova, Mila ¹

¹ CMLA, ENS Cachan, CNRS, UniverSud, 61, avenue President Wilson, 94230 Cachan, France

Comptes Rendus. Mathématique, Tome 349 (2011) no. 21-22, pp. 1145-1150.

Résumé
Abstract

Nous analysons des objectifs $F_{d}$ 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 \times N$ et de rang M où $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 $\ddot{u}$ dont la longueur du support ne dépasse pas $M - 1$ comme un minimiseur (local) strict de $F_{d}$ où $d = A \ddot{u}$ .

We analyze objectives $F_{d}$ combining a quadratic data-fidelity and a weighted $ℓ_{0}$ penalty. Data d are generated using a full column rank $M \times 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 $\ddot{u}$ with support shorter than $M - 1$ as a strict (local) minimizer of $F_{d}$ where $d = A \ddot{u}$ .

Reçu le : 2011-05-23
Accepté le : 2011-08-18
Publié le : 2011-10-05

DOI : 10.1016/j.crma.2011.08.011

Affiliations des auteurs :

Nikolova, Mila ¹

¹ CMLA, ENS Cachan, CNRS, UniverSud, 61, avenue President Wilson, 94230 Cachan, France

@article{CRMATH_2011__349_21-22_1145_0,
     author = {Nikolova, Mila},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2011.08.011/}
}

TY  - JOUR
AU  - Nikolova, Mila
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2011.08.011/
DO  - 10.1016/j.crma.2011.08.011
LA  - en
ID  - CRMATH_2011__349_21-22_1145_0
ER  -

%0 Journal Article
%A Nikolova, Mila
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2011.08.011/
%R 10.1016/j.crma.2011.08.011
%G en
%F CRMATH_2011__349_21-22_1145_0

Nikolova, Mila. Solve exactly an under determined linear system by minimizing least squares regularized with an $ {\ell }_{0}$ penalty. Comptes Rendus. Mathématique, Tome 349 (2011) no. 21-22, pp. 1145-1150. doi : 10.1016/j.crma.2011.08.011. http://www.numdam.org/articles/10.1016/j.crma.2011.08.011/

Bibliographie
Cité par

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

[2] Bruckstein, A.M.; Donoho, D.L.; Elad, M. 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] Davis, G.; Mallat, S.; Avellaneda, M. Adaptive greedy approximations, Constructive Approximation, Volume 13 (1997) no. 1, pp. 57-98

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

[5] Gasso, G.; Rakotomamonjy, A.; Canu, S. 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] Haupt, J.; Nowak, R. Signal reconstruction from noisy random projections, IEEE Transactions on Information Theory, Volume 52 (2006) no. 9, pp. 4036-4048

[7] Liu, Y.; Wu, Y. 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] Lv, J.; Fan, Y. A unified approach to model selection and sparse recovery using regularized least squares, The Annals of Statistics, Volume 37 (2009) no. 6A

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

[10] Miller, A.J. 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] Neumann, J.; Schörr, C.; Steidl, G. Combined SVM-based feature selection and classification, Machine Learning, Volume 61 (2005), pp. 129-150

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

Cité par Sources :