Low-Rank Matrix Recovery from Row-and-Column Affine Measurements

16/06/2016 - 12:00


We propose a new measurement scheme for low-rank matrix recovery, where each measurement 

is a linear combination of elements in one row or one column of the unknown matrix. 


This setting arises naturally in applications but current algorithms, developed for standard matrix recovery problems, do not perform well in this case, hence the need for developing new algorithms and theory. 


We propose a simple algorithm for the problem based on Singular Value Decomposition (SVD) and least-squares (LS), which we term SVLS. We prove favourable theoretical guarantees for our algorithm 

for the noiseless and noisy case, compared to standard matrix completion measurement schemes 

and algorithms.  Simulations show improved speed and accuracy, including for the problem of unknown rank estimation.  


Our results suggest that the proposed row-and-column measurements scheme, together with our recovery algorithm, may provide a powerful framework for affine matrix recovery.


Time permitting, I will describe also progress on other data analysis projects for sparse and structured-sparse data, including a new group-sparse clustering algorithm