Compressed Sensing, Matrix Completion And Their Applications In Signal Processing

Compressed sensing and matrix completion are inverse problem under sparse constraint, compressed sensing solves the underdetermined equations using the sparsity of signal or its coefficients in the transform domain, matrix completion solves the underdetemined equations using the low-rank property of matrix. The core of compressed sensing theory are sparse representation of signal, the design of observation matrix and reconstruction algorithm. Signal or its coefficients are more sparse, the restricted isometry constant of compressed sensing matrix is smaller, then the performance of compressed sensing is better. The core of matrix completion theory are low-rank property, incoherence property and reconstruction algorithm. Looking for good reconstruction algorithm has been a research focus in the matrix completion theory. In addition, the application field of compressed sensing has expand widely, but the application field of matrix completion is still in its infancy. It is very important and meaningful to excavate the application of matrix completion and the combined application of compressed sensing and matrix completion. The main work and innovation of the dissertation can be generalized as follows.(1) Research the reconstruction algorithm of compressed sensing and matrix completion, and improve the reconstruction theorem of matrix completion. Reconstruction algorithm is an important part of compressed sensing and matrix completion, which directly influences the performance of compressed sensing and matrix completion. This dissertation first analyzes reconstruction algorithms in compressed sensing: BP, OMP, CoSa MP, SP, IHT. And reconstruction algorithms in matrix completion: SVT, ADMiRA, SVP. Experimental results show that the performance of BP and SVP are better than other several reconstruction algorithms. Secondly, this dissertation analyzes reconstruction theorem of matrix completion, points out that theorem requires two parameters, the number of parameters not only is more but also their values are not easy to determine. This dissertation combines the original reconstruction theorem and incoherence constant, points forward a new reconstruction theorem, which needs a single parameter. This parameter is easy decided, so it can effectively promote the research of matrix completion.(2) Sparse representation is not suitable in signal currently. The coefficients of most nature signal under sparse transform are not absolute sparse, which means that except for finite large coefficients, the rest is not zero, but is close to zero. This kind of coefficients are called approximate sparse or compressible, which affects the reconstruction performance of compressed sensing greatly. This dissertation designs discrete cosine transform based on thresholding matrix(DCTTM). Compared with DCT basis, the coefficients of signal under DCTTM basis are closer to the ideal absolute sparse.(3) The structure of observation matrix is an important role in compressed sensing, which directly affects the signal compression and reconstruction. The adaptive observation matrix in this dissertation uses gaussian random matrix as original matrix, and makes an new observation matrix under the partial positional information of sparse coefficients. Meanwhile, it reduces the observed value by reducing the row vector of observation. This dissertation verifies that the performance of adaptive observation matrix is better than gaussian random observation matrix through theory and experiments.(4) The reconstruction algorithm of matrix completion has a common defect which needs the rank of original matrix. It is difficult to predict the rank of unknown matrix in matrix completion, just as prediction the sparsity of original signal in compressed sensing, which greatly limits the application of matrix completion. The projected gradient descent based on soft thresholding(STPGD) in this dissertation iteratives based on projected gradient descent, and predicts the rank of low-rank matrix used soft thresholding. This algorithm not only reduces the computational complexity, but also improves the precision of the reconstruction solution. This dissertation analyzes the reconstruction performance of STPGD from convergence and computational complexity, and demonstrates the iteration number of STPGD when achieving scheduled reconstruction error.(5) Research the joint application of CS and MC in dynamic image processing. Compressed sensing has been widely used in magnetic resonance imaging, single pixel camera, face recognition and image super-resolution reconstruction. And matrix completion also achieves initial results in collaborative filtering, system identification, sensor network and spectrum sensing. But the joint application of CS and MC is still in its infancy. This dissertation mainly analyzes the joint application of CS and MC in dynamic image processing, and introduces the principal component pursuit(PCP).