Finding the sparsest solution to underdetermined systems of linear equationsy= Φxis NP-hard in general. We show here that for systems with “typical”/“random” Φ, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra. Our proposal, Stagewise Orthogonal Matching Pursuit (StOMP), successively transforms the signal into a negligible residual. Starting with initial residualr0=y, at thes-th stage it forms the “matched filter” ΦTrs-1, identifies all coordinates with amplitudes exceeding a specially chosen threshold, solves a least-squares problem using the selected coordinates, and subtracts the least-squares fit, producing a new residual. After a fixed number of stages (e.g., 10), it stops. In contrast to Orthogonal Matching Pursuit (OMP), many coefficients can enter the model at each stage in StOMP while only one enters per stage in OMP; and StOMP takes a fixed number of stages (e.g., 10), while OMP can take many (e.g.,n). We give both theoretical and empirical support for the large-system effectiveness of StOMP. We give numerical examples showing that StOMP rapidly and reliably finds sparse solutions in compressed sensing, decoding of error-correcting codes, and overcomplete representation.

The minimum lscr1-norm solution to an underdetermined system of linear equationsy=Axis often, remarkably, also the sparsest solution to that system. This sparsity-seeking property is of interest in signal processing and information transmission. However, general-purpose optimizers are much too slow for lscr1minimization in many large-scale applications.In this paper, the Homotopy method, originally proposed by Osborne et al. and Efron et al., is applied to the underdetermined lscr1-minimization problem min parxpar1subject toy=Ax. Homotopy is shown to run much more rapidly than general-purpose LP solvers when sufficient sparsity is present. Indeed, the method often has the followingk-step solution property: if the underlying solution has onlyknonzeros, the Homotopy method reaches that solution in onlykiterative steps. Thisk-step solution property is demonstrated for several ensembles of matrices, including incoherent matrices, uniform spherical matrices, and partial orthogonal matrices. These results imply that Homotopy may be used to rapidly decode error-correcting codes in a stylized communication system with a computational budget constraint. The approach also sheds light on the evident parallelism in results on lscr1minimization and orthogonal matching pursuit (OMP), and aids in explaining the inherent relations between Homotopy, least angle regression (LARS), OMP, and polytope faces pursuit.

We briefly recall previous literature about the interaction between sparsity and /spl lscr/ /sup 1/ minimization. We then discuss /spl lscr/ /sup 1/ minimization in geometry separation, in compressed sensing, and in compressed sensing of separable signals.

Block coders are among the most common compression tools available for still images and video sequences. Their low computational complexity along with their good performance make them a popular choice for compression of natural images. Yet, at low bit-rates, block coders introduce visually annoying artifacts into the image. One approach that alleviates this problem is to downsample the image, apply the coding algorithm, and interpolate back to the original resolution. In this paper, we consider the use of optimal decimation and interpolation filters in this scheme. We first consider only optimization of the interpolation filter, by formulating the problem as least-squares minimization. We then consider the joint optimization over both the decimation and the interpolation filters, using the variable projection method. The experimental results presented clearly exhibit a significant improvement over other approaches.

The emerging video coding standard MPEG-4 enables various content-based functionalities for multimedia applications. To support such functionalities, as well as to improve coding efficiency, MPEG-4 relies on a decomposition of each frame of an image sequence into video object planes (VOP). Each VOP corresponds to a single moving object in the scene. This paper presents a new method for automatic segmentation of moving objects in image sequences for VOP extraction. We formulate the problem as graph labeling over a region adjacency graph (RAG), based on motion information. The label field is modeled as a Markov random field (MRF). An initial spatial partition of each frame is obtained by a fast, floating-point based implementation of the watershed algorithm. The motion of each region is estimated by hierarchical region matching. To avoid inaccuracies in occlusion areas, a novel motion validation scheme is presented. A dynamic memory, based on object tracking, is incorporated into the segmentation process to maintain temporal coherence of the segmentation. Finally, a labeling is obtained by maximization of the a posteriori probability of the MRF using motion information, spatial information and the memory. The optimization is carried out by highest confidence first (HCF). Experimental results for several video sequences demonstrate the effectiveness of the proposed approach.

This paper addresses the problem of segmentation of moving objects in image sequences, which is of key importance in content-based applications. We transform the problem into a graph labeling problem over a region adjacency graph (RAG), by introducing a Markov random field (MRF) model based on spatio-temporal information. The initial partition is obtained by fast, color-based watershed segmentation. The motion of each region is estimated and validated in a hierarchical framework. A dynamic memory, based on object tracking, is incorporated into the segmentation process to maintain temporal coherence. The performance of the algorithm is evaluated on several real-world image sequences.