TY - GEN

T1 - Low-rank matrix completion with geometric performance guarantees

AU - Dai, Wei

AU - Kerman, Ely

AU - Milenkovic, Olgica

PY - 2011/8/18

Y1 - 2011/8/18

N2 - The low-rank matrix completion problem can be stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. There exist several low-complexity algorithms for low-rank matrix completion which focus on the minimization of the Frobenius norm of the matrix projection residue. This optimization framework has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we propose a geometric objective function to replace the Frobenius norm: the new objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. Furthermore, using the geometric objective function and a simple gradient descent procedure, we are able to preclude the existence of local minimizers, and hence establish strong performance guarantees for special completion scenarios, which do not require matrix incoherence or large matrix size.

AB - The low-rank matrix completion problem can be stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. There exist several low-complexity algorithms for low-rank matrix completion which focus on the minimization of the Frobenius norm of the matrix projection residue. This optimization framework has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we propose a geometric objective function to replace the Frobenius norm: the new objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. Furthermore, using the geometric objective function and a simple gradient descent procedure, we are able to preclude the existence of local minimizers, and hence establish strong performance guarantees for special completion scenarios, which do not require matrix incoherence or large matrix size.

KW - geometry

KW - low rank

KW - matrix completion

UR - http://www.scopus.com/inward/record.url?scp=80051617357&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80051617357&partnerID=8YFLogxK

U2 - 10.1109/ICASSP.2011.5947164

DO - 10.1109/ICASSP.2011.5947164

M3 - Conference contribution

AN - SCOPUS:80051617357

SN - 9781457705397

T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

SP - 3740

EP - 3743

BT - 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings

T2 - 36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011

Y2 - 22 May 2011 through 27 May 2011

ER -