Finding a point in the relative interior of a polyhedron, with applications to compressed sensing

Abstract : Consider a system of finitely many equalities and inequalities that depend linearly on N variables. We propose an algorithm that provably finds a point in the relative interior of the polyhedron described by these constraints, thus allowing the identification of the affine dimension of this set (often smaller than N). It can therefore be employed to find a starting point for the class of interior-point methods for linear programming, and also as a preprocessor for the latter problem class that removes superfluous or implied constraints, with strong guarantees of convergence. In particular, it may be used to solve the feasibility problems that occur in sparse approximation when prior information is included (Donoho & Tanner, 2008).
Type de document :
Communication dans un congrès
Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00369400
Contributeur : Ist Rennes <>
Soumis le : jeudi 19 mars 2009 - 16:12:32
Dernière modification le : jeudi 26 octobre 2017 - 16:34:02
Document(s) archivé(s) le : mardi 8 juin 2010 - 20:13:02

Fichier

90.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00369400, version 1

Collections

Citation

Coralia Cartis, Gould Nicholas I. M.. Finding a point in the relative interior of a polyhedron, with applications to compressed sensing. Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009. 〈inria-00369400〉

Partager

Métriques

Consultations de la notice

267

Téléchargements de fichiers

76