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

Mila Nikolova

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

Mila Nikolova ¹

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

Comptes Rendus. Mathématique, Volume 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 :

Mila Nikolova ¹

¹ 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/

Bibliographie
Cité par

[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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Properties of a single vortex solution in a rotating Bose Einstein condensate

Amandine Aftalion; Robert L. Jerrard

C. R. Math (2003)

Local minimizers of one-dimensional variational problems and obstacle problems

Mikhail A. Sychev

C. R. Math (2008)

Ginzburg–Landau minimizers with prescribed degrees: dependence on domain

Leonid Berlyand; Petru Mironescu

C. R. Math (2003)