Computable Performance Analysis of Recovering Signals with Low-dimensional Structures

The last decade witnessed the burgeoning development in the reconstruction of signals by exploiting their low-dimensional structures, particularly, the sparsity, the block-sparsity, the low-rankness, and the low-dimensional manifold structures of general nonlinear data sets. The reconstruction performance of these signals relies heavily on the structure of the sensing matrix/operator. In many applications, there is a flexibility to select the optimal sensing matrix among a class of them. A prerequisite for optimal sensing matrix design is the computability of the performance for different recovery algorithms. I present a computational framework for analyzing the recovery performance of signals with low-dimensional structures. I define a family of goodness measures for arbitrary sensing matrices as the optimal values of a set of optimization problems. As one of the primary contributions of this work, I associate the goodness measures with the fixed points of functions defined by a series of linear programs, second-order cone programs, or semidefinite programs, depending on the specific problem. This relation with the fixed-point theory, together with a bisection search implementation, yields efficient algorithms to compute the goodness measures with global convergence guarantees. As a by-product, we implement efficient algorithms to verify sufficient conditions for exact signal recovery in the noise-free case. The implementations perform orders-of-magnitude faster than the state-of-the-art techniques. The utility of these goodness measures lies in their relation with the reconstruction performance. I derive bounds on the recovery errors of convex relaxation algorithms in terms of these goodness measures. Using tools from empirical processes and generic chaining, I analytically demonstrate that as long as the number of measurements are relatively large, these goodness measures are bounded away from zeros for a large class of random sensing matrices, a result parallel to the probabilistic analysis of the restricted isometry property. Numerical experiments show that, compared with the restricted isometry based performance bounds, our error bounds apply to a wider range of problems and are tighter, when the sparsity levels of the signals are relatively low. I expect that computable performance bounds would open doors for wide applications in compressive sensing, sensor arrays, radar, MRI, image processing, computer vision, collaborative filtering, control, and many other areas where low-dimensional signal structures arise naturally.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical and Systems Engineering

Year dc:date.available

2011

Author dc:creator

• Tang, Gongguo

Contributors dc:contributor

• Arye Nehorai

• Electrical Engineering
• Statistics
• Mathematics
• block-sparsity recovery
• compressive sensing
• fixed point theory
• low-rank matrix recovery
• semidefinite programming
• sparsity recovery

Language dc:language

English (en)

DOI

https://doi.org/10.7936/K7862DH7

OAI identifier oai:identifier

oai:openscholarship.wustl.edu:etd-1646