Skip to Main content Skip to Navigation
Conference papers

Gradient Polytope Faces Pursuit for large scale sparse recovery problems

Abstract : Polytope Faces Pursuit is a greedy algorithm that performs Basis Pursuit with similar order complexity to Orthogonal Matching Pursuit. The algorithm adds one basis vector at a time and adopts a path-following approach based on the geometry of the polar polytope associated with the dual Linear Program. Its initial implementation uses the method of Cholesky factorization to update the solution vector at each step, which can be computationally expensive for solving large scale problems as it requires the succesive storage of large matrices. In this paper, we present a different approach using directional updates to estimate the solution vector at each time. The proposed method uses the gradient descent method, reducing the memory requirements and computational complexity. We demonstrate the application of this Gradient Polytope Faces Pursuit algorithm to a source separation problem.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/inria-00565791
Contributor : Jules Espiau de Lamaestre <>
Submitted on : Monday, February 14, 2011 - 3:42:18 PM
Last modification on : Monday, February 14, 2011 - 3:42:18 PM

Links full text

Identifiers

Collections

Citation

Aris Gretsistas, Ivan Damnjanovic, Mark D. Plumbley. Gradient Polytope Faces Pursuit for large scale sparse recovery problems. Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, Mar 2010, dallas, United States. pp.2030 -2033, ⟨10.1109/ICASSP.2010.5494955⟩. ⟨inria-00565791⟩

Share

Metrics

Record views

125