Most of the existing works on provable guarantees for low-rank matrix
completion algorithms rely on some unrealistic assumptions such that matrix
entries are sampled randomly or the sampling pattern has a specific structure.
In this work, we establish theoretical guarantee for the exact and approximate
low-rank matrix completion problems which can be applied to any deterministic
sampling schemes. For this, we introduce a graph having observed entries as its
edge set, and investigate its graph properties involving the performance of the
standard constrained nuclear norm minimization algorithm. We theoretically and
experimentally show that the algorithm can be successful as the observation
graph is well-connected and has similar node degrees. Our result can be viewed
as an extension of the works by Bhojanapalli and Jain [2014] and Burnwal and
Vidyasagar [2020], in which the node degrees of the observation graph were
assumed to be the same. In particular, our theory significantly improves their
results when the underlying matrix is symmetric.

该论文针对低秩矩阵完成算法的理论保证存在严格且近似的情况，可以应用于任何确定性采样计划。通过引入一个图形来解决观察条目的性能问题，论文从理论和实验角度论证了算法的成功性。

来自一般确定性采样模式的矩阵补全

Matrix Completion from General Deterministic Sampling Patterns

Stein Variational Gradient Descent (SVGD) is a nonparametric particle-based
deterministic sampling algorithm. Despite its wide usage, understanding the
theoretical properties of SVGD has remained a challenging problem. For sampling
from a Gaussian target, the SVGD dynamics with a bilinear kernel will remain
Gaussian as long as the initializer is Gaussian. Inspired by this fact, we
undertake a detailed theoretical study of the Gaussian-SVGD, i.e., SVGD
projected to the family of Gaussian distributions via the bilinear kernel, or
equivalently Gaussian variational inference (GVI) with SVGD. We present a
complete picture by considering both the mean-field PDE and discrete particle
systems. When the target is strongly log-concave, the mean-field Gaussian-SVGD
dynamics is proven to converge linearly to the Gaussian distribution closest to
the target in KL divergence. In the finite-particle setting, there is both
uniform in time convergence to the mean-field limit and linear convergence in
time to the equilibrium if the target is Gaussian. In the general case, we
propose a density-based and a particle-based implementation of the
Gaussian-SVGD, and show that several recent algorithms for GVI, proposed from
different perspectives, emerge as special cases of our unified framework.
Interestingly, one of the new particle-based instance from this framework
empirically outperforms existing approaches. Our results make concrete
contributions towards obtaining a deeper understanding of both SVGD and GVI.

通过使用正态分布初始化器逼近高斯目标样本并使用密度和基于粒子的实现方法，证明了 Stein Variational Gradient Descent (SVGD) 及其变体的特性，包括线性收敛和性能优越性，这对于深入理解 SVGD 和 Gaussian variational inference (GVI) 的相关性提供了具体贡献。