Lowrank regularization and solution uniqueness in overparameterized matrix sensing
[edit]
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:930940, 2020.
Abstract
We consider the question whether algorithmic choices in overparameterized linear matrix factorization introduce implicit lowrank regularization.We focus on the noiseless matrix sensing scenario over lowrank positive semidefinite (PSD) matrices over the reals, with a sensing mechanism that satisfies restricted isometry properties.Surprisingly, it was recently argued that for recovery of PSD matrices, gradient descent over a squared, \textit{fullrank} factorized space introduces implicit lowrank regularization.Thus, a clever choice of the recovery algorithm avoids the need for explicit lowrank regularization. In this contribution, we prove that in fact, under certain conditions, the PSD constraint by itself is sufficient to lead to a unique lowrank matrix recovery, without explicit or implicit regularization.Therefore, under these conditions, the set of PSD matrices that are consistent with the observed data, is a singleton, regardless of the algorithm used. Our numerical study indicates that this result is general and extends to cases beyond the those covered by the proof.
Related Material


