Matrix rank minimizing subject to affine constraints arises in many
application areas, ranging from signal processing to machine learning. Nuclear
norm is a convex relaxation for this problem which can recover the rank exactly
under some restricted and theoretically interesting conditions. However, for
many real-world applications, nuclear norm approximation to the rank function
can only produce a result far from the optimum. To seek a solution of higher
accuracy than the nuclear norm, in this paper, we propose a rank approximation
based on Logarithm-Determinant. We consider using this rank approximation for
subspace clustering application. Our framework can model different kinds of
errors and noise. Effective optimization strategy is developed with theoretical
guarantee to converge to a stationary point. The proposed method gives
promising results on face clustering and motion segmentation tasks compared to
the state-of-the-art subspace clustering algorithms.

本文提出一种基于 Logarithm-Determinant 的等级逼近方法，用于子空间聚类应用，并开发有效的优化策略，以实现收敛到一个稳定点，并在人脸聚类和运动分割任务方面比目前最先进的子空间聚类算法具有更好的效果。

平滑秩近似算法鲁棒子空间聚类

Robust Subspace Clustering via Smoothed Rank Approximation

In many applications that require matrix solutions of minimal rank, the
underlying cost function is non-convex leading to an intractable, NP-hard
optimization problem. Consequently, the convex nuclear norm is frequently used
as a surrogate penalty term for matrix rank. The problem is that in many
practical scenarios there is no longer any guarantee that we can correctly
estimate generative low-rank matrices of interest, theoretical special cases
notwithstanding. Consequently, this paper proposes an alternative empirical
Bayesian procedure build upon a variational approximation that, unlike the
nuclear norm, retains the same globally minimizing point estimate as the rank
function under many useful constraints. However, locally minimizing solutions
are largely smoothed away via marginalization, allowing the algorithm to
succeed when standard convex relaxations completely fail. While the proposed
methodology is generally applicable to a wide range of low-rank applications,
we focus our attention on the robust principal component analysis problem
(RPCA), which involves estimating an unknown low-rank matrix with unknown
sparse corruptions. Theoretical and empirical evidence are presented to show
that our method is potentially superior to related MAP-based approaches, for
which the convex principle component pursuit (PCP) algorithm (Candes et al.,
2011) can be viewed as a special case.

本文提出了一种基于变分近似的经验贝叶斯程序，用于低秩矩阵估计，与核范数不同的是，该方法保留了很多有用约束下与秩函数相同的全局最小点估计。该方法适用于广泛的低秩学习应用，特别是强健主成分分析问题（RPCA）。

一种基于经验贝叶斯方法的非凸秩最小化算法

Non-Convex Rank Minimization via an Empirical Bayesian Approach

We consider the problem of computing the rank of an m x n matrix A over a
field. We present a randomized algorithm to find a set of r = rank(A) linearly
independent columns in \~O(|A| + r^\omega) field operations, where |A| denotes
the number of nonzero entries in A and \omega < 2.38 is the matrix
multiplication exponent. Previously the best known algorithm to find a set of r
linearly independent columns is by Gaussian elimination, with running time
O(mnr^{\omega-2}). Our algorithm is faster when r < max(m,n), for instance when
the matrix is rectangular. We also consider the problem of computing the rank
of a matrix dynamically, supporting the operations of rank one updates and
additions and deletions of rows and columns. We present an algorithm that
updates the rank in \~O(mn) field operations. We show that these algorithms can
be used to obtain faster algorithms for various problems in numerical linear
algebra, combinatorial optimization and dynamic data structure.

本文介绍了一种随机算法来计算矩阵的秩，可以在线性时间内找到一组线性无关的列，并解决了动态矩阵更新问题。这种方法可以有效地应用于数值线性代数、组合优化和动态数据结构中。