



01552nas a2200109   4500008004100000245008900041210006900130520116300199100002701362700001601389856003701405       2018                        eng d00aImplicit regularization and solution uniqueness in over-parameterized matrix sensing0 aImplicit regularization and solution uniqueness in overparameter3 a<p>We consider whether algorithmic choices in over-parameterized linear matrix factorization introduce implicit regularization. We focus on noiseless matrix sensing over rank-r positive semi-definite (PSD) matrices in Rn&times;n, with a sensing mechanism that satisfies the restricted isometry property (RIP). The algorithm we study is that of \emph{factored gradient descent}, where we model the low-rankness and PSD constraints with the factorization UU⊤, where U&isin;Rn&times;r. Surprisingly, recent work argues that the choice of r&le;n is not pivotal: even setting U&isin;Rn&times;n is sufficient for factored gradient descent to find the rank-r solution, which suggests that operating over the factors leads to an implicit regularization. In this note, we provide a different perspective. We show that, in the noiseless case, under certain conditions, the PSD constraint by itself is sufficient to lead to a unique rank-r matrix recovery, without implicit or explicit low-rank regularization. \emph{I.e.}, under assumptions, the set of PSD matrices, that are consistent with the observed data, is a singleton, irrespective of the algorithm used.</p>1 aKyrillidis, Anastasios1 aKalev, Amir  uhttps://arxiv.org/abs/1806.02046