| HAL-Inria | Publications, software ... of Inria's scientists |
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).
Cited literature [4 references]
https://hal.inria.fr/inria-00369400
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Thursday, March 19, 2009 - 4:12:32 PM
Last modification on : Wednesday, November 24, 2021 - 9:54:07 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:13:02 PM
Contributor : Ist Rennes Connect in order to contact the contributor
Submitted on : Thursday, March 19, 2009 - 4:12:32 PM
Last modification on : Wednesday, November 24, 2021 - 9:54:07 AM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:13:02 PM
File
90.pdf
Files produced by the author(s)