Iteratively reweighted least squares minimization for sparse recovery
Pourquoi ce travail est-il dans la base ?
Une base qui oublie comment elle a trouvé un travail ne peut pas être vérifiée. Voici les voies qui ont admis celui-ci.
Aucune affiliation canadienne. Une base fondée sur la seule affiliation (le devis habituel) n'aurait jamais vu ce travail. C'est l'un des travaux qui justifient l'inversion de la base.
Résumé
Abstract Under certain conditions (known as the restricted isometry property , or RIP) on the m × N matrix Φ (where m < N ), vectors x ∈ ℝ N that are sparse (i.e., have most of their entries equal to 0) can be recovered exactly from y := Φ x even though Φ −1 ( y ) is typically an ( N − m )—dimensional hyperplane; in addition, x is then equal to the element in Φ −1 ( y ) of minimal 𝓁 1 ‐norm. This minimal element can be identified via linear programming algorithms. We study an alternative method of determining x , as the limit of an iteratively reweighted least squares (IRLS) algorithm. The main step of this IRLS finds, for a given weight vector w , the element in Φ −1 ( y ) with smallest 𝓁 2 ( w )‐norm. If x ( n ) is the solution at iteration step n , then the new weight w ( n ) is defined by w := [| x | 2 + ε ] −1/2 , i = 1, …, N , for a decreasing sequence of adaptively defined ε n ; this updated weight is then used to obtain x ( n + 1) and the process is repeated. We prove that when Φ satisfies the RIP conditions, the sequence x ( n ) converges for all y , regardless of whether Φ −1 ( y ) contains a sparse vector. If there is a sparse vector in Φ −1 ( y ), then the limit is this sparse vector, and when x ( n ) is sufficiently close to the limit, the remaining steps of the algorithm converge exponentially fast ( linear convergence in the terminology of numerical optimization). The same algorithm with the “heavier” weight w = [| x | 2 + ε ] −1+τ/2 , i = 1, …, N , where 0 < τ < 1, can recover sparse solutions as well; more importantly, we show its local convergence is superlinear and approaches a quadratic rate for τ approaching 0. © 2009 Wiley Periodicals, Inc.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
La notice
- Revue
- Communications on Pure and Applied Mathematics
- Thématique
- Sparse and Compressive Sensing Techniques
- Domaine
- Engineering
- Établissements canadiens
- —
- Organismes subventionnaires
- Army Research OfficeOffice of Naval ResearchEuropean CommissionGoddard Space Flight CenterYork UniversityPrinceton UniversityDeutscher Akademischer AustauschdienstNational Science Foundation
- Mots-clés
- MathematicsRestricted isometry propertyCombinatoricsHyperplaneIteratively reweighted least squaresLimit pointNorm (philosophy)Sequence (biology)Limit (mathematics)Matrix (chemical analysis)WeightAlgorithmElement (criminal law)Compressed sensingDiscrete mathematicsApplied mathematicsNon-linear least squaresMathematical analysisPure mathematicsLie algebraEstimation theory
- Résumé présent dans OpenAlex
- oui