  The Schatten-$p$ quasi-norm with $p\in(0,1)$ has recently gained considerable
attention in various low-rank matrix estimation problems offering significant
benefits over relevant convex heuristics such as the nuclear norm. However, due
to the nonconvexity of the Schatten-$p$ quasi-norm, minimization suffers from
two major drawbacks: 1) the lack of theoretical guarantees and 2) the high
computational cost which is demanded for the minimization task even for trivial
tasks such as finding stationary points. In an attempt to reduce the high
computational cost induced by Schatten-$p$ quasi-norm minimization, variational
forms, which are defined over smaller-size matrix factors whose product equals
the original matrix, have been proposed. Here, we propose and analyze a novel
variational form of Schatten-$p$ quasi-norm which, for the first time in the
literature, is defined for any continuous value of $p\in(0,1]$ and decouples
along the columns of the factorized matrices. The proposed form can be
considered as the natural generalization of the well-known variational form of
the nuclear norm to the nonconvex case i.e., for $p\in(0,1)$. The resulting
formulation gives way to SVD-free algorithms thus offering lower computational
complexity than the one that is induced by the original definition of the
Schatten-$p$ quasi-norm. A local optimality analysis is provided which
shows~that we can arrive at a local minimum of the original Schatten-$p$
quasi-norm problem by reaching a local minimum of the matrix factorization
based surrogate problem. In addition, for the case of the squared Frobenius
loss with linear operators obeying the restricted isometry property (RIP), a
rank-one update scheme is proposed, which offers a way to escape poor local
minima. Finally, the efficiency of our approach is empirically shown on a
matrix completion problem.

Numerical Analysis;Numerical Analysis