Skip to main content

Max-norm optimization for robust matrix recovery

Author(s): Fang, Ethan X; Liu, Han; Toh, Kim-Chuan; Zhou, Wen-Xin

To refer to this page use:
Abstract: This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform sampling assumption imposed for the widely used nuclear-norm penalized approach, and makes low-rank matrix recovery feasible in more practical settings. Theoretically, we prove that the proposed estimator achieves fast rates of convergence under different settings. Computationally, we propose an alternating direction method of multipliers algorithm to efficiently compute the estimator, which bridges a gap between theory and practice of machine learning methods with max-norm regularization. Further, we provide thorough numerical studies to evaluate the proposed method using both simulated and real datasets.
Publication Date: 2018
Citation: Fang, Ethan X., Han Liu, Kim-Chuan Toh, and Wen-Xin Zhou. "Max-norm optimization for robust matrix recovery." Mathematical Programming 167, no. 1 (2018): 5-35. doi:10.1007/s10107-017-1159-y
DOI: doi:10.1007/s10107-017-1159-y
ISSN: 0025-5610
EISSN: 1436-4646
Pages: 5 - 35
Type of Material: Journal Article
Journal/Proceeding Title: Mathematical Programming
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.