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

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 with support shorter than M−1 as a strict (local) minimizer of Fd where .

Résumé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 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 dont la longueur du support ne dépasse pas M−1 comme un minimiseur (local) strict de Fd où .