A novel variational form of the Schatten-p quasi-norm
A novel variational form of the Schatten-p quasi-norm
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Paris V. Giampouras;R. Vidal;A. Rontogiannis;B. Haeffele
中科院分区：
文献类型：
--
作者：
Paris V. Giampouras;R. Vidal;A. Rontogiannis;B. Haeffele
具有$p\in(0,1)$的Schatten-$p$准范数最近在各种低秩矩阵估计问题中获得了相当大的关注，它比相关的凸启发式方法（如核范数）具有显著的优势。然而，由于Schatten-$p$准范数的非凸性，最小化存在两个主要缺点：1)缺乏理论保证；2)即使是寻找平稳点这样的琐碎任务，最小化任务也需要很高的计算成本。为了降低Schatten-$p$拟范数最小化所引起的高计算成本，提出了在较小尺寸的矩阵因子上定义的变分形式，其乘积等于原始矩阵。本文提出并分析了Schatten-$p$拟范数的一种新的变分形式，在文献中首次定义了任意连续的$p\in(0,1]$和沿分解矩阵列的解耦。所提出的形式可以被认为是众所周知的核范数变分形式对非凸情况的自然推广，即对于$p\in(0,1)$。由此产生的公式让位于无svd的算法，从而提供比由Schatten-$p$准范数的原始定义引起的计算复杂度更低的算法。给出了局部最优性分析，表明通过求解矩阵分解代理问题的局部极小值，可以得到原Schatten-$p$拟范数问题的局部极小值。此外，对于符合限制等距性质（RIP）的线性算子的平方Frobenius损失，提出了一种秩一更新方案，该方案提供了一种避免局部极值的方法。最后，在一个矩阵补全问题上验证了该方法的有效性。
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.