| Recent theoretical study shows that the sparsest solution to an underdetermined linear system is unique, provided the solution vector is sufficiently sparse, and the operator matrix has sufficiently incoherent column vectors. In addition, efficient algorithms have been discovered to find such solutions. This intriguing result opens a new door for many potential applications. In this thesis, we study the design of a class of greedy algorithms that are extremely efficient, e.g., Orthogonal Matching Pursuit (OMP). These greedy algorithms suffer from a stability issue that the greedy selection approach always make locally optimal decisions, thereby easily biasing and mistaking the solutions in particular under data noise. We propose a solution approach that in designing greedy algorithms, new constraints can be devised by leveraging application-specific insights and incorporated into the algorithms. Given that sparse recovery problems by definition are underdetermined, introducing additional constraints can significantly improve the stability of greedy algorithms, yet retain their efficiency.;We demonstrate the effectiveness of the proposed solution approach in two example applications: image classification with semi-supervised machine learning, and medium access control in multiuser MIMO networks. In image classification, we show that by introducing a nonnegativity constraint in both feature dictionary learning and feature extraction, we are able to obtain effective feature-space representations for classification purposes, especially when labeled training samples are limited. Our solution approach outperforms the classical OMP approach in classification accuracy, and is competitive with other best-known methods, while requiring much less computation. In multiuser MIMO networks, we show that sparse recovery allows us to identify transmitting host stations and estimate channel statistics from overlapping symbol sequences. The receive antenna diversity on a base station leads to a "same-support" constraint that the received signals share a same set of source transmitters. This constraint can significantly improve the convergence speed of the recovery algorithm. Moreover, this new way of concurrent channel estimation has implications on medium access strategy in multiuser MIMO for delivering throughput scalable to the available number of antennas installed on a base station. |
