Low-rank matrix recovery: blind deconvolution and efficient sampling of correlated signals

Low-rank recovery;Structured randomness;Blind deconvolution;Efficient sampling

Ahmed, Ali ; Romberg, Justin K. Electrical and Computer Engineering Rozell, Christopher J. Davenport, Mark A. Koltchinskii, Vladimir Lanterman, Aaron D. ; Romberg, Justin K.

University:Georgia Institute of Technology

Department:Electrical and Computer Engineering

关键词: Low-rank recovery;    Structured randomness;    Blind deconvolution;    Efficient sampling;   

Others  :  https://smartech.gatech.edu/bitstream/1853/50226/1/AHMED-DISSERTATION-2013.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Low-dimensional signal structures naturally arise in a large set of applications in various fields such as medical imaging, machine learning, signal, and array processing. A ubiquitous low-dimensional structure in signals and images is sparsity, and a new sampling theory; namely, compressive sensing, proves that the sparse signals and images can be reconstructed from incomplete measurements. The signal recovery is achieved using efficient algorithms such as \ell_1-minimization. Recently, the research focus has spun-off to encompass other interesting low-dimensional signal structures such as group-sparsity and low-rank structure. This thesis considers low-rank matrix recovery (LRMR) from various structured-random measurement ensembles. These results are then employed for the in depth investigation of the classical blind-deconvolution problem from a new perspective, and for the development of a framework for the efficient sampling of correlated signals (the signals lying in a subspace). In the first part, we study the blind deconvolution; separation of two unknown signals by observing their convolution. We recast the deconvolution of discrete signals w and x as a rank-1 matrix wx* recovery problem from a structured random measurement ensemble. The convex relaxation of the problem leads to a tractable semidefinite program. We show, using some of the mathematical tools developed recently for LRMR, that if we assume the signals convolved with one another live in known subspaces, then this semidefinite relaxation is provably effective. In the second part, we design various efficient sampling architectures for signals acquired using large arrays. The sampling architectures exploit the correlation in the signals to acquire them at a sub-Nyquist rate. The sampling devices are designed using analog components with clear implementation potential. For each of the sampling scheme, we show that the signal reconstruction can be framed as an LRMR problem from a structured-random measurement ensemble. The signals can be reconstructed using the familiar nuclear-norm minimization. The sampling theorems derived for each of the sampling architecture show that the LRMR framework produces the Shannon-Nyquist performance for the sub-Nyquist acquisition of correlated signals.In the final part, we study low-rank matrix factorizations using randomized linear algebra. This specific method allows us to use a least-squares program for the reconstruction of the unknown low-rank matrix from the samples of its row and column space. Based on the principles of this method, we then design sampling architectures that not only acquire correlated signals efficiently but also require a simple least-squares program for the signal reconstruction. A theoretical analysis of all of the LRMR problems above is presented in this thesis, which provides the sufficient measurements required for the successful reconstruction of the unknown low-rank matrix, and the upper bound on the recovery error in both noiseless and noisy cases. For each of the LRMR problem, we also provide a discussion of a computationally feasible algorithm, which includes a least-squares-based algorithm, and some of the fastest algorithms for solving nuclear-norm minimization.