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.
Type de document :
Communication dans un congrès
Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, Mar 2010, dallas, United States. pp.2030 -2033, 2010, 〈10.1109/ICASSP.2010.5494955〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00565791
Contributeur : Jules Espiau de Lamaestre <>
Soumis le : lundi 14 février 2011 - 15:42:18
Dernière modification le : lundi 14 février 2011 - 15:42:18

Identifiants

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, 2010, 〈10.1109/ICASSP.2010.5494955〉. 〈inria-00565791〉

Partager

Métriques

Consultations de la notice

60