Study On Sparse Reconstruction And Low-rank Matrix Recovery

Many natural signals have concise expressions through appropriate basis transformation,and can be accurately restored from these expressions as well,such as wavelet transformation for images,Fourier transformation for narrow-band signals,singular value decomposition for low-rank matrices,etc.Recent studies have shown that,with the property of sparse or lowrank,the original data of high dimension can be expressed,processed,analyzed and inferred,namely the sparse reconstruction and low rank matrix recovery technology.This technology is widely used in a number of areas such as reconstruction of high dimensional sparse signal,restoration of missing pixels in images,completion of unknown elements for a low-rank matrix in an advertising recommendation system,sparse / low-rank representation in object detection and tracking in computer vision,sparse / low-rank subspace clustering in machine learning,and so on.In this dissertation,we study the models and algorithms of sparse reconstruction and lowrank matrix recovery,and achieve the following innovative results:1)In the field of array signal processing,we generalize the sparse reconstruction method for direction of arrival(DOA)estimation of point sources to that of distributed sources.The traditional point source DOA estimation algorithms such as MUSIC,ESPRIT,usually require a computational intensive spectrum peak searching for the key parameters.To address this issue,in recent years,sparse reconstruction is applied to the point source DOA estimation,which avoids the spectrum peak searching and thus significantly reduces the amount of computation.Due to the fact that the far field distributed sources are sparse in the entire angular space,we attempt to apply sparse reconstruction to the distributed signal sources.The traditional DOA estimation algorithms for distributed sources have the disadvantage of the computational intensive spectrum peak searching as well.In addition,different from the point sources,they assume certain angular signal and angular power density functions,such as Gauss distribution,uniform distribution and triangular distribution.These two functions represent the spatial distribution of the signal source,which may not be predictable in practice.Therefore,the DOA estimation of the distributed source usually estimates the center angle of arrival and several distribution parameters only.In this dissertation,we propose an algorithm to estimate the spatial distribution curve of the distributed source.The distribution curve is considered as a sparse vector which needs to be reconstructed.Different from the existing algorithms,our algorithm can obtain the whole spatial distribution curve,which provides more abundant and comprehensive information.2)We propose a sparse and low-rank combination model which allows the regularization term to be non-convex and non-smooth.Many existing models only explore the property of either sparse or low-rank.Models that explore both properties do not get much attention due to less application scenarios.Although several algorithms study the coexistence of both properties,they restrict the regularization terms to be convex to simplify the models.However,the coexistence of both sparse and low-rank properties is useful in some practical applications such as the user-item rating matrix in advertising recommendation system and the covariance matrix of block diagonal structure in subspace clustering problem.In addition,recent studies have shown that non-convex regularization can achieve solutions with better sparse / low-rank property.In view of this situation,we propose a more general sparse and low-rank model,which not only allows composite sparse and low-rank regularizers,but also allows them to be non-convex and non-smooth,filling the gap in current research literature.In order to overcome the difficulty that solving models with composite non-convex regularizers requires a computational intensive inner iteration,we adopt a technique called “approximate average method”,which calculates an approximate solution at each iteration and thus avoids the above mentioned dilemma.We show that although the solution used at each step is only an approximation,it will eventually converge to the true solution of the problem.We also discuss the issue of avoiding the local minimum.3)We proposes an accelerated reweighted nuclear norm minimization algorithm,which can efficiently solve the Schatten-p non-convex model.The Schatten-p model is a low-rank matrix recovery model;and the reweighted nuclear norm minimization algorithm is newly proposed in recent years.We prove that the algorithm is essentially a special case of the block-wise coordinate descend method.At the same time,we notice that an essential step in the original algorithm can be interpreted as solving an optimization sub-problem.Based on the above analysis,we improve this step by making the objective function descend further at every iteration,thus accelerating the whole procedure.We prove that the modified algorithm is guaranteed to converge to a stationary point of the Schatten-p non-convex model.Numerical results show that our algorithm requires distinctly fewer iterations and less computational time than the original one to achieve the same(or very close)accuracy,in some problem instances even require only about 50% computational time of the original one,and is also notably faster than several other state-of-the-art algorithms.