Factoring a matrix into two low rank matrices is at the heart of many
problems. The problem of matrix completion especially uses it to decompose a
sparse matrix into two non sparse, low rank matrices which can then be used to
predict unknown entries of the original matrix. We present a scalable and
decentralized approach in which instead of learning two factors for the
original input matrix, we decompose the original matrix into a grid blocks,
each of whose factors can be individually learned just by communicating
(gossiping) with neighboring blocks. This eliminates any need for a central
server. We show that our algorithm performs well on both synthetic and real
datasets.

本研究提出了一种基于分布式学习的去中心化方法来分解稀疏矩阵为低密度矩阵，避免了中央服务器的需求，并在多个合成和真实数据集上验证了算法的性能。

通过流言算法实现矩阵完形填空的二维分解方法

A two-dimensional decomposition approach for matrix completion through  gossip

Trace norm regularization is a widely used approach for learning low rank
matrices. A standard optimization strategy is based on formulating the problem
as one of low rank matrix factorization which, however, leads to a non-convex
problem. In practice this approach works well, and it is often computationally
faster than standard convex solvers such as proximal gradient methods.
Nevertheless, it is not guaranteed to converge to a global optimum, and the
optimization can be trapped at poor stationary points. In this paper we show
that it is possible to characterize all critical points of the non-convex
problem. This allows us to provide an efficient criterion to determine whether
a critical point is also a global minimizer. Our analysis suggests an iterative
meta-algorithm that dynamically expands the parameter space and allows the
optimization to escape any non-global critical point, thereby converging to a
global minimizer. The algorithm can be applied to problems such as matrix
completion or multitask learning, and our analysis holds for any random
initialization of the factor matrices. Finally, we confirm the good performance
of the algorithm on synthetic and real datasets.

本文中提出了一种迭代元算法，通过动态扩展参数空间，避免优化陷入局部最优解，从而更好地解决低秩矩阵因式分解问题及其应用。

重新审视低秩矩阵分解的迹范数正则化

Reexamining Low Rank Matrix Factorization for Trace Norm Regularization

We study the Riemannian optimization methods on the embedded manifold of low
rank matrices for the problem of matrix completion, which is about recovering a
low rank matrix from its partial entries. Assume $m$ entries of an $n\times n$
rank $r$ matrix are sampled independently and uniformly with replacement. We
first prove that with high probability the Riemannian gradient descent and
conjugate gradient descent algorithms initialized by one step hard thresholding
are guaranteed to converge linearly to the measured matrix provided
\begin{align*} m\geq C_\kappa n^{1.5}r\log^{1.5}(n), \end{align*} where
$C_\kappa$ is a numerical constant depending on the condition number of the
underlying matrix. The sampling complexity has been further improved to
\begin{align*} m\geq C_\kappa nr^2\log^{2}(n) \end{align*} via the resampled
Riemannian gradient descent initialization. The analysis of the new
initialization procedure relies on an asymmetric restricted isometry property
of the sampling operator and the curvature of the low rank matrix manifold.
Numerical simulation shows that the algorithms are able to recover a low rank
matrix from nearly the minimum number of measurements.

研究嵌入低秩矩阵流形的黎曼优化方法在矩阵补全问题上的应用和收敛性，其中采样复杂度能进一步通过重新采样的黎曼梯度下降初始化方法减小，这取决于采样算子的像的非对称限制性同构性质和低秩矩阵流形的曲率。

Riemannian 优化在低秩矩阵补全中的保证

Guarantees of Riemannian Optimization for Low Rank Matrix Completion

Regularization by the sum of singular values, also referred to as the trace
norm, is a popular technique for estimating low rank rectangular matrices. In
this paper, we extend some of the consistency results of the Lasso to provide
necessary and sufficient conditions for rank consistency of trace norm
minimization with the square loss. We also provide an adaptive version that is
rank consistent even when the necessary condition for the non adaptive version
is not fulfilled.

本文研究了套索正则化与奇异值的和（trace norm）正则化在估计低秩矩阵中的应用，并扩展了套索的一些一致性结果以提供必要和充分的条件，以实现具有方块差异的迹范数最小化的秩一致性，同时提供了一种自适应版本，即使不满足非自适应版本的必要条件，也可以实现秩一致性。