Journal article
Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
Journal of machine learning research, Vol.20, 97
01/01/2019
Abstract
In this paper, we develop a relative error bound for nuclear norm regularized matrix completion, with the focus on the completion of full-rank matrices. Under the assumption that the top eigenspaces of the target matrix are incoherent, we derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix. Although multiple works have been devoted to analyzing the recovery error of full-rank matrix completion, their error bounds are usually additive, making it impossible to obtain the perfect recovery case and more generally difficult to leverage the skewed distribution of eigenvalues. Our analysis is built upon the optimality condition of the regularized formulation and existing guarantees for low-rank matrix completion. To the best of our knowledge, this is the first relative bound that has been proved for the regularized formulation of matrix completion.
Details
- Title: Subtitle
- Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion
- Creators
- Lijun Zhang - Nanjing UniversityTianbao Yang - Univ Iowa, Dept Comp Sci, Iowa City, IA 52242 USARong Jin - Alibaba Grp, Machine Intelligence Technol, Bellevue, WA 98004 USAZhi-Hua Zhou - Nanjing University
- Resource Type
- Journal article
- Publication Details
- Journal of machine learning research, Vol.20, 97
- Publisher
- Microtome Publ
- ISSN
- 1532-4435
- eISSN
- 1533-7928
- Number of pages
- 22
- Grant note
- Collaborative Innovation Center of Novel Software Technology and Industrialization BK20160658; 2017QNRC001 / JiangsuSF 61861146001 / NSFC-NRF Joint Research Project 2018YFB-1004300 / National Key RAMP;D Program of China
- Language
- English
- Date published
- 01/01/2019
- Academic Unit
- Computer Science
- Record Identifier
- 9984259407802771
Metrics
4 Record Views