Low-rank matrix completion with geometric performance guarantees

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings
Pages3740-3743
Number of pages4
DOIs
StatePublished - Aug 18 2011
Event36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Prague, Czech Republic
Duration: May 22 2011May 27 2011

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
ISSN (Print)1520-6149

Other

Other36th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011
CountryCzech Republic
CityPrague
Period5/22/115/27/11

Keywords

  • geometry
  • low rank
  • matrix completion

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Low-rank matrix completion with geometric performance guarantees'. Together they form a unique fingerprint.

  • Cite this

    Dai, W., Kerman, E., & Milenkovic, O. (2011). Low-rank matrix completion with geometric performance guarantees. In 2011 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011 - Proceedings (pp. 3740-3743). [5947164] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings). https://doi.org/10.1109/ICASSP.2011.5947164