Skip to Main content Skip to Navigation
Conference papers

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).
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00369400
Contributor : Ist Rennes <>
Submitted on : Thursday, March 19, 2009 - 4:12:32 PM
Last modification on : Wednesday, October 14, 2020 - 4:06:28 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:13:02 PM

File

90.pdf
Files produced by the author(s)

Identifiers

  • 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. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Inria Rennes - Bretagne Atlantique, Apr 2009, Saint Malo, France. ⟨inria-00369400⟩

Share

Metrics

Record views

298

Files downloads

218