Matrix factorization is an inference problem that has acquired importance due
to its vast range of applications that go from dictionary learning to
recommendation systems and machine learning with deep networks. The study of
its fundamental statistical limits represents a true challenge, and despite a
decade-long history of efforts in the community, there is still no closed
formula able to describe its optimal performances in the case where the rank of
the matrix scales linearly with its size. In the present paper, we study this
extensive rank problem, extending the alternative 'decimation' procedure that
we recently introduced, and carry out a thorough study of its performance.
Decimation aims at recovering one column/line of the factors at a time, by
mapping the problem into a sequence of neural network models of associative
memory at a tunable temperature. Though being sub-optimal, decimation has the
advantage of being theoretically analyzable. We extend its scope and analysis
to two families of matrices. For a large class of compactly supported priors,
we show that the replica symmetric free entropy of the neural network models
takes a universal form in the low temperature limit. For sparse Ising prior, we
show that the storage capacity of the neural network models diverges as
sparsity in the patterns increases, and we introduce a simple algorithm based
on a ground state search that implements decimation and performs matrix
factorization, with no need of an informative initialization.

通过扩展我们最近引入的替代性 “减少” 程序，我们对广泛秩问题进行研究，并对其性能进行了深入研究。

对称矩阵分解的削减方案

The Decimation Scheme for Symmetric Matrix Factorization

We study a principal component analysis problem under the spiked Wishart
model in which the structure in the signal is captured by a class of
union-of-subspace models. This general class includes vanilla sparse PCA as
well as its variants with graph sparsity. With the goal of studying these
problems under a unified statistical and computational lens, we establish
fundamental limits that depend on the geometry of the problem instance, and
show that a natural projected power method exhibits local convergence to the
statistically near-optimal neighborhood of the solution. We complement these
results with end-to-end analyses of two important special cases given by path
and tree sparsity in a general basis, showing initialization methods and
matching evidence of computational hardness. Overall, our results indicate that
several of the phenomena observed for vanilla sparse PCA extend in a natural
fashion to its structured counterparts.

通过研究一种在尖峰维沙特模型下的主成分分析问题，我们揭示了信号中的结构通过一类子空间模型予以捕捉。在统计和计算统一的视角下，我们建立了依赖于问题实例几何结构的基本限制，并展示了一种自然的投影幂法在解的统计可接近最优邻域上表现出的局部收敛性。我们通过分析两个重要特例，即基于路径和树稀疏性的初始方法和匹配证据的计算难度，来补充这些结果。总体而言，我们的结果表明，多个针对普通稀疏主成分分析观察到的现象自然地扩展到其结构化对应物中。