Nuit Blanche: CS: Greedy Signal Recovery Review, Motion Segmentation, Efficient Sampling and Stable Reconstruction,

Friday, December 12, 2008

CS: Greedy Signal Recovery Review, Motion Segmentation, Efficient Sampling and Stable Reconstruction,

I found three papers related to CS:

Greedy Signal Recovery Review by Deanna Needell, Joel Tropp and Roman Vershynin. The abstract reads:

The two major approaches to sparse recovery are L1-minimization and greedy methods. Recently, Needell and Vershynin developed Regularized Orthogonal Matching Pursuit (ROMP) that has bridged the gap between these two approaches. ROMP is the first stable greedy algorithm providing uniform guarantees. Even more recently, Needell and Tropp developed the stable greedy algorithm Compressive Sampling Matching Pursuit (CoSaMP). CoSaMP provides uniform guarantees and improves upon the stability bounds and RIC requirements of ROMP. CoSaMP offers rigorous bounds on computational cost and storage. In many cases, the running time is just O(N logN), where N is the ambient dimension of the signal. This review summarizes these major advances.

ROMP and CoSaMP codes are accessible from the reconstruction section of the Big Picture. Let us also note the importance of the Restricted Isometry Constant.

Moshe Mishali, Yonina Eldar and Joel Tropp just released Efficient Sampling and Stable Reconstruction of Wide Band Sparse Analog Signals , the asbtract reads:

Periodic nonuniform sampling is a known method to sample spectrally sparse signals below the Nyquist rate. This strategy relies on the implicit assumption that the individual samplers are exposed to the entire frequency range. This assumption becomes impractical for wideband sparse signals. The current paper proposes an alternative sampling stage that does not require a full-band front end. Instead, signals are captured with an analog front end that consists of a bank of multipliers and lowpass filters whose cutoff ismuch lower than the Nyquist rate. The problem of recovering the original signal from the low-rate samples can be studied within the framework of compressive sampling. An appropriate parameter selection ensures that the samples uniquely determine the analog input. Moreover, the analog input can be stably reconstructed with digital algorithms. Numerical experiments support the theoretical analysis.

The attendant talk is here. In a different direction, Shankar Rao, Roberto Tron, Rene Vidal, and Yi Ma just released

Motion Segmentation in the Presence of Outlying, Incomplete, and Corrupted Trajectories . The abstract reads:

In this paper, we study the problem of segmenting tracked feature point trajectories of multiple moving objects in an image sequence. Using the affine camera model, this problem can be cast as the problem of segmenting samples drawn from multiple linear subspaces. In practice, due to limitations of the tracker, occlusions, and the presence of nonrigid objects in the scene, the obtained motion trajectories may contain grossly mistracked features, missing entries, or corrupted entries. In this paper, we develop a robust subspace separation scheme that deals with these practical issues in a unified mathematical framework. Our methods draw strong connections between lossy compression, rank minimization, and sparse representation. We test our methods extensively on the Hopkins155 motion segmentation database and other motion sequences with outliers and missing data. We compare the performance of our methods to state-of-the-art motion segmentation methods based on expectation-maximization and spectral clustering. For data without outliers or missing information, the results of our methods are on par with the state-of-the-art results, and in many cases exceed them. In addition, our methods give surprisingly good performance in the presence of the three types of pathological trajectories mentioned above. All code and results are publicly available at http://perception.csl.uiuc.edu/coding/motion/.

Yi Ma and his team continue on doing wonders. Here they use the result in rank minimization and CS to provide robust trackers over missing data.

And finally, here is a section of papers and presentations not strictly exactly focused on Compressed Sensing but rather that make use or reference Compressive as a neighboring technique. There the presentation entitled Pseudospectral Fourier reconstruction with IPRM by Karlheinz Gröchenig and Tomasz Hrycak.

Also, Arxiv now allows a full search in the text of the papers in its library. Here is a list of paper that mention Compressive Sensing without Compressive Sensing being the main subject of the paper: