Compressive sensing algorithms for recovery of sparse and low rank signals - Mukund Sriram Narasimhan (Nanyang Technological University, 2021)
Many natural signals are atomic, i.e., the signals may be represented in some low dimensional space due to their inherent structure. Two most common atomic structures are sparsity and low rank. A sparse signal (vector/matrix) has very few nonzero entries. A low rank matrix has very small rank in comparison to its dimensions. These structures were first exploited in compressive sensing (CS) and matrix completion respectively. CS is a sampling scheme which aims to recover a sparse signal from reduced number of measurements using an appropriate recovery algorithm. In matrix completion we have a low rank matrix with missing entries, and the aim is to find the missing entries. The concepts were extended to de-mixing (separating sparse and low rank components from a mixture) and phase retrieval (recovery of signal from magnitude measurements alone). In these applications, the data exhibits both low rank and sparse properties. We propose to study new signal models to which these concepts can be applied and to develop corresponding recovery algorithms. Towards this goal, we have worked on the following problems. Distributed compressive Sensing (DCS) is an extension of CS from single vector to multiple signal vectors. We consider DCS in the context of joint sparse model (JSM). It consists of an ensemble of correlated signals (from different sensors in a network) that can be decomposed into a common component and an innovation component (both sparse). We write this model as a sum of a sparse and low rank matrix and develop an algorithm to recover the components from the compressed measurements. This model is further recast as a basis pursuit problem for ease of computation. The proposed method requires less number of measurements and recovery accuracy is found to be better than the existing algorithms for JSM. Hyper-spectral data are collection of images that are acquired simultaneously from a scene in a few hundred adjacent frequency bands. It can be represented as a matrix which is both sparse and low rank. Compressive acquisition of this type of signals can result in substantial savings in terms of sensor cost and data storage. In order to recover the signal from CS type measurements, we need to solve a convex optimization problem that has both sparse and low rank penalty in the objective. Inspired by iterative re-weighted least squares, we develop an approach that involves finding a quadratic approximation for the objective. It is an iterative two step procedure where we solve a quadratic program (QP) and use the result to update the weight matrix of the objective. This approach simplifies computational complexity of recovery process and allows the use of efficient QP solvers which are widely available.