Advanced Factorization Approaches for Low-Rank Matrix Recovery

Description

In many real-world applications including recommender system, genotype imputation, computer vision, and hyperspectral remote sensing, the data can be modelled by amtimes  n incomplete matrix whose rank is r>min(m,n).  Hence there is a need to complete the missing matrix entries with the use of the possibly noisy observations and low-rank property. In principle, low-rank matrix recovery is directly formulated as a constrained rank minimization problem but it is computationally infeasible. Approximating the rank minimization as nuclear norm minimization, followed by realization with semi-definite relaxation or singular value decomposition (SVD), is a viable approach. However, their involved calculations increase drastically withmand/orn. While matrix completion methods based on truncated SVD and matrix factorization are much simpler in complexity, they require the rankrto be known, which may not be true in practical scenarios. On the other hand, to cope with possible deviations from the assumed data model, two popular ways are introducing an extra sparse matrix, and applying M-estimation, yet they may result in limited robustness, and high computational requirement, respectively. Furthermore, for simultaneous recovery of multiple matrices such as in multi-frame video completion and hyperspectral image restoration, the existing solutions merely apply the matrix-to-vector approach to form a big incomplete matrix with column lengthmnfor retrieval. Nevertheless, the vectorization procedure destroys the inherent spatial/structural information in the two-dimensional data and leads to enormous computations particularly for largemn. The goal of this research is to explore advanced signal processing and optimization techniques to devise factorization based algorithms for fast, accurate and robust matrix recovery. By representing a matrix as a sum of outer products without knowing the value ofr, our key idea is to find the basis vectors of the underlying matrix according to the observed entries, and gradually increase the vector number to achieve automatic rank detection. Under various uncertain conditions, we will robustify this adaptive rank-one matrix bi-factorization methodology based on M-estimation but reformulated with an implicit regularizer for attaining computational efficiency. To avoid vectorization in multiple matrix recovery, we will open up the matrix-to-matrix approach via tri-factorization, such that all involved matrices are products of three matrices where two of them remain the same in each decomposition. Convergence analysis of the developed methods will also be provided. Moreover, comparison with the state-of-the-art schemes in terms of restoration performance and computational complexity will be conducted for different applications using real data.