AISTATS 2021poster13 citations
On the Absence of Spurious Local Minima in Nonlinear Low-Rank Matrix Recovery Problems
Abstract
The restricted isometry property (RIP) is a well-known condition that guarantees the absence of spurious local minima in low-rank matrix recovery problems with linear measurements. In this paper, we introduce a novel property named bound difference property (BDP) to study low-rank matrix recovery problems with nonlinear measurements. Using RIP and BDP jointly, we propose a new criterion to certify the nonexistence of spurious local minima in the rank-1 case, and prove that it leads to a much stronger theoretical guarantee than the existing bounds on RIP.
BibTeX
@InProceedings{pmlr-v130-bi21a,
title = { On the Absence of Spurious Local Minima in Nonlinear Low-Rank Matrix Recovery Problems },
author = {Bi, Yingjie and Lavaei, Javad},
booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics},
pages = {379--387},
year = {2021},
editor = {Banerjee, Arindam and Fukumizu, Kenji},
volume = {130},
series = {Proceedings of Machine Learning Research},
month = {13--15 Apr},
publisher = {PMLR},
pdf = {http://proceedings.mlr.press/v130/bi21a/bi21a.pdf},
url = {https://proceedings.mlr.press/v130/bi21a.html},
abstract = { The restricted isometry property (RIP) is a well-known condition that guarantees the absence of spurious local minima in low-rank matrix recovery problems with linear measurements. In this paper, we introduce a novel property named bound difference property (BDP) to study low-rank matrix recovery problems with nonlinear measurements. Using RIP and BDP jointly, we propose a new criterion to certify the nonexistence of spurious local minima in the rank-1 case, and prove that it leads to a much stronger theoretical guarantee than the existing bounds on RIP. }
}