This paper considers the problem of minimizing the sum of a smooth function
and the Schatten-$p$ norm of the matrix. Our contribution involves proposing
accelerated iteratively reweighted nuclear norm methods designed for solving
the nonconvex low-rank minimization problem. Two major novelties characterize
our approach. Firstly, the proposed method possesses a rank identification
property, enabling the provable identification of the "correct" rank of the
stationary point within a finite number of iterations. Secondly, we introduce
an adaptive updating strategy for smoothing parameters. This strategy
automatically fixes parameters associated with zero singular values as
constants upon detecting the "correct" rank while quickly driving the rest
parameters to zero. This adaptive behavior transforms the algorithm into one
that effectively solves smooth problems after a few iterations, setting our
work apart from existing iteratively reweighted methods for low-rank
optimization. We prove the global convergence of the proposed algorithm,
guaranteeing that every limit point of the iterates is a critical point.
Furthermore, a local convergence rate analysis is provided under the
Kurdyka-{\L}ojasiewicz property. We conduct numerical experiments using both
synthetic and real data to showcase our algorithm's efficiency and superiority
over existing methods.

该研究考虑了平滑函数和矩阵的 Schatten-p 范数之和的最小化问题，并提出了用于解决非凸低秩最小化问题的加速迭代重新加权核范数方法，其主要创新包括具有秩识别特性的方法和自适应更新策略，通过快速将参数驱动为零，将算法转化为能有效解决平滑问题的算法。

高效低秩身份识别的迭代加速核范数最小化

Efficient Low-rank Identification via Accelerated Iteratively Reweighted  Nuclear Norm Minimization

The Schatten-$p$ norm ($0<p<1$) has been widely used to replace the nuclear
norm for better approximating the rank function. However, existing methods are
either 1) not scalable for large scale problems due to relying on singular
value decomposition (SVD) in every iteration, or 2) specific to some $p$
values, e.g., $1/2$, and $2/3$. In this paper, we show that for any $p$, $p_1$,
and $p_2 >0$ satisfying $1/p=1/p_1+1/p_2$, there is an equivalence between the
Schatten-$p$ norm of one matrix and the Schatten-$p_1$ and the Schatten-$p_2$
norms of its two factor matrices. We further extend the equivalence to multiple
factor matrices and show that all the factor norms can be convex and smooth for
any $p>0$. In contrast, the original Schatten-$p$ norm for $0<p<1$ is
non-convex and non-smooth. As an example we conduct experiments on matrix
completion. To utilize the convexity of the factor matrix norms, we adopt the
accelerated proximal alternating linearized minimization algorithm and
establish its sequence convergence. Experiments on both synthetic and real
datasets exhibit its superior performance over the state-of-the-art methods.
Its speed is also highly competitive.

本文通过建立 Schatten-p norm 与 factor matrices 中的 Schatten-p1 和 Schatten-p2 norm 之间的等价性，进一步扩展到多个因子矩阵中，表明其所有的因子 norm 都可以是任意 p 的凸光滑的，从而利用凸性提出加速的 proximal alternating linearized minimization algorithm，并在合成和实际数据集上通过矩阵补全任务展示了其优越性能。

一种蕴含 Schatten-$p$ 范数的凸代理函数

A Unified Convex Surrogate for the Schatten-$p$ Norm

This work presents a general framework for solving the low rank and/or sparse
matrix minimization problems, which may involve multiple non-smooth terms. The
Iteratively Reweighted Least Squares (IRLS) method is a fast solver, which
smooths the objective function and minimizes it by alternately updating the
variables and their weights. However, the traditional IRLS can only solve a
sparse only or low rank only minimization problem with squared loss or an
affine constraint. This work generalizes IRLS to solve joint/mixed low rank and
sparse minimization problems, which are essential formulations for many tasks.
As a concrete example, we solve the Schatten-$p$ norm and $\ell_{2,q}$-norm
regularized Low-Rank Representation (LRR) problem by IRLS, and theoretically
prove that the derived solution is a stationary point (globally optimal if
$p,q\geq1$). Our convergence proof of IRLS is more general than previous one
which depends on the special properties of the Schatten-$p$ norm and
$\ell_{2,q}$-norm. Extensive experiments on both synthetic and real data sets
demonstrate that our IRLS is much more efficient.

本文提出了一个解决低秩和 / 或稀疏矩阵最小化问题的一般框架，使用迭代重新加权最小二乘（IRLS）方法来解决混合低秩和稀疏最小化问题，例如用于解决 Schatten-p 规范和 ell_2,q-norm 规范的低秩表示问题，理论证明了所获得的解为静止点，并在合成和实际数据集上进行了广泛的实验以证明其有效性。