Many important tasks of large-scale recommender systems can be naturally cast
as testing multiple linear forms for noisy matrix completion. These problems,
however, present unique challenges because of the subtle bias-and-variance
tradeoff of and an intricate dependence among the estimated entries induced by
the low-rank structure. In this paper, we develop a general approach to
overcome these difficulties by introducing new statistics for individual tests
with sharp asymptotics both marginally and jointly, and utilizing them to
control the false discovery rate (FDR) via a data splitting and symmetric
aggregation scheme. We show that valid FDR control can be achieved with
guaranteed power under nearly optimal sample size requirements using the
proposed methodology. Extensive numerical simulations and real data examples
are also presented to further illustrate its practical merits.

通过引入新的统计量和利用数据分割和对称聚合方案，该研究开发了一种通用方法来控制多元线性形式的测试的误发现率，并展示了在几乎最优的样本量需求下可以实现有效的 FDR 控制和保证的功效。

嘈杂矩阵补全的线性形式多重检验

Multiple Testing of Linear Forms for Noisy Matrix Completion

Noisy matrix completion aims at estimating a low-rank matrix given only
partial and corrupted entries. Despite substantial progress in designing
efficient estimation algorithms, it remains largely unclear how to assess the
uncertainty of the obtained estimates and how to perform statistical inference
on the unknown matrix (e.g.~constructing a valid and short confidence interval
for an unseen entry).
This paper takes a step towards inference and uncertainty quantification for
noisy matrix completion. We develop a simple procedure to compensate for the
bias of the widely used convex and nonconvex estimators. The resulting
de-biased estimators admit nearly precise non-asymptotic distributional
characterizations, which in turn enable optimal construction of confidence
intervals\,/\,regions for, say, the missing entries and the low-rank factors.
Our inferential procedures do not rely on sample splitting, thus avoiding
unnecessary loss of data efficiency. As a byproduct, we obtain a sharp
characterization of the estimation accuracy of our de-biased estimators, which,
to the best of our knowledge, are the first tractable algorithms that provably
achieve full statistical efficiency (including the preconstant). The analysis
herein is built upon the intimate link between convex and nonconvex
optimization --- an appealing feature recently discovered by
\cite{chen2019noisy}.

本文提出了一种补偿广泛使用的凸估计器偏差的简单程序，从而实现了对噪声矩阵完成的不确定性和推断，并产生了近乎精确的非渐近分布表征，进而实现了对缺失条目和低秩因子的置信区间的最优构建。

噪声矩阵补全的推断和不确定性量化

Inference and Uncertainty Quantification for Noisy Matrix Completion

We consider the problem of noisy matrix completion, in which the goal is to
reconstruct a structured matrix whose entries are partially observed in noise.
Standard approaches to this underdetermined inverse problem are based on
assuming that the underlying matrix has low rank, or is well-approximated by a
low rank matrix. In this paper, we propose a richer model based on what we term
the "permutation-rank" of a matrix. We first describe how the classical
non-negative rank model enforces restrictions that may be undesirable in
practice, and how and these restrictions can be avoided by using the richer
permutation-rank model. Second, we establish the minimax rates of estimation
under the new permutation-based model, and prove that surprisingly, the minimax
rates are equivalent up to logarithmic factors to those for estimation under
the typical low rank model. Third, we analyze a computationally efficient
singular-value-thresholding algorithm, known to be optimal for the low-rank
setting, and show that it also simultaneously yields a consistent estimator for
the low-permutation rank setting. Finally, we present various structural
results characterizing the uniqueness of the permutation-rank decomposition,
and characterizing convex approximations of the permutation-rank polytope.

本文提出了基于置换秩的模型，可以避免传统基于非负秩模型的限制，并证明了该模型下的估计极小值等价于传统低秩模型，进而分析了一个基于奇异值阈值的有效算法，并展示了多样的结构结果来表征置换秩分解的唯一性和凸逼近。

低置换秩矩阵：结构性质与噪声完整性

Low Permutation-rank Matrices: Structural Properties and Noisy  Completion

This paper examines a general class of noisy matrix completion tasks where
the goal is to estimate a matrix from observations obtained at a subset of its
entries, each of which is subject to random noise or corruption. Our specific
focus is on settings where the matrix to be estimated is well-approximated by a
product of two (a priori unknown) matrices, one of which is sparse. Such
structural models - referred to here as "sparse factor models" - have been
widely used, for example, in subspace clustering applications, as well as in
contemporary sparse modeling and dictionary learning tasks. Our main
theoretical contributions are estimation error bounds for sparsity-regularized
maximum likelihood estimators for problems of this form, which are applicable
to a number of different observation noise or corruption models. Several
specific implications are examined, including scenarios where observations are
corrupted by additive Gaussian noise or additive heavier-tailed (Laplace)
noise, Poisson-distributed observations, and highly-quantized (e.g., one-bit)
observations. We also propose a simple algorithmic approach based on the
alternating direction method of multipliers for these tasks, and provide
experimental evidence to support our error analyses.

本文针对具有噪声的矩阵完成任务进行了研究，特别关注于估计由两个未知矩阵的乘积组成的矩阵，其中一个是稀疏矩阵的情况，提出了基于稀疏因子模型的正则化最大似然估计的误差界和算法方法。