Friday, 11:00 - 11:25 h, Room: H 1028


Prateek Jain
Orthogonal matching pursuit with replacement

Coauthors: Inderjit S. Dhillon, Ambuj Tewari


In this paper, we consider the problem of compressed sensing where the goal is to recover almost all the sparse vectors using a small number of fixed linear measurements. For this problem, we propose a novel partial hard-thresholding operator that leads to a general family of iterative algorithms. While one extreme of the family yields well known hard thresholding algorithms like ITI (Iterative Thresholding with Inversion) and HTP (Hard Thresholding Pursuit), the other end of the spectrum leads to a novel algorithm that we call Orthogonal Matching Pursuit with Replacement (OMPR). OMPR, like the classic greedy algorithm OMP, adds exactly one coordinate to the support at each iteration, based on the correlation with the current residual. However, unlike OMP, OMPR also removes one coordinate from the support. This simple change allows us to prove that OMPR has the best known guarantees for sparse recovery in terms of the Restricted Isometry Property (a condition on the measurement matrix). Our proof techniques are novel and flexible enough to also permit the tightest known analysis of popular iterative algorithms such as CoSaMP and Subspace Pursuit.


Talk 2 of the invited session Fri.1.H 1028
"Greedy algorithms for sparse optimization" [...]
Cluster 21
"Sparse optimization & compressed sensing" [...]


  The main criterion for them is your ability to repay any Payday Loans In Wisconsin, they are not interested in your previous attempts, the current one is all that matters. What can cause long-term use of Viagra? In the network and other sources of information, there is no reliable data on the long-term use of Viagra and its negative effects on the body.