Block-wise missing data poses significant challenges in real-world data
imputation tasks. Compared to scattered missing data, block-wise gaps
exacerbate adverse effects on subsequent analytic and machine learning tasks,
as the lack of local neighboring elements significantly reduces the
interpolation capability and predictive power. However, this issue has not
received adequate attention. Most SOTA matrix completion methods appeared less
effective, primarily due to overreliance on neighboring elements for
predictions. We systematically analyze the issue and propose a novel matrix
completion method ``BlockEcho" for a more comprehensive solution. This method
creatively integrates Matrix Factorization (MF) within Generative Adversarial
Networks (GAN) to explicitly retain long-distance inter-element relationships
in the original matrix. Besides, we incorporate an additional discriminator for
GAN, comparing the generator's intermediate progress with pre-trained MF
results to constrain high-order feature distributions. Subsequently, we
evaluate BlockEcho on public datasets across three domains. Results demonstrate
superior performance over both traditional and SOTA methods when imputing
block-wise missing data, especially at higher missing rates. The advantage also
holds for scattered missing data at high missing rates. We also contribute on
the analyses in providing theoretical justification on the optimality and
convergence of fusing MF and GAN for missing block data.

提出一种名为 “BlockEcho” 的新型矩阵补全方法，通过在生成对抗网络中创造性地整合矩阵分解和鉴别器，以解决分块缺失数据的问题，并在公共数据集上验证其在高缺失率下优于传统和现有方法的性能表现。

BlockEcho: 维持长程依赖性以对块级缺失数据进行补全

BlockEcho: Retaining Long-Range Dependencies for Imputing Block-Wise  Missing Data

Given only a few observed entries from a low-rank matrix $X$, matrix
completion is the problem of imputing the missing entries, and it formalizes a
wide range of real-world settings that involve estimating missing data.
However, when there are too few observed entries to complete the matrix, what
other aspects of the underlying matrix can be reliably recovered? We study one
such problem setting, that of "one-sided" matrix completion, where our goal is
to recover the right singular vectors of $X$, even in the regime where
recovering the left singular vectors is impossible, which arises when there are
more rows than columns and very few observations. We propose a natural
algorithm that involves imputing the missing values of the matrix $X^TX$ and
show that even with only two observations per row in $X$, we can provably
recover $X^TX$ as long as we have at least $\Omega(r^2 d \log d)$ rows, where
$r$ is the rank and $d$ is the number of columns. We evaluate our algorithm on
one-sided recovery of synthetic data and low-coverage genome sequencing. In
these settings, our algorithm substantially outperforms standard matrix
completion and a variety of direct factorization methods.

本篇论文主要研究的是在因为缺少有效的观察数据，无法完成左奇异向量解法时，如何利用仅有的观察值来恢复右奇异向量以及相关的矩阵，并且提出了一个适用于 $X^TX$ 的算法，针对合成数据和低覆盖基因组测序，该算法得到了很好的效果。

每行两个观测点的单侧矩阵补全

One-sided Matrix Completion from Two Observations Per Row

We propose a novel method for imputing missing data by adapting the
well-known Generative Adversarial Nets (GAN) framework. Accordingly, we call
our method Generative Adversarial Imputation Nets (GAIN). The generator (G)
observes some components of a real data vector, imputes the missing components
conditioned on what is actually observed, and outputs a completed vector. The
discriminator (D) then takes a completed vector and attempts to determine which
components were actually observed and which were imputed. To ensure that D
forces G to learn the desired distribution, we provide D with some additional
information in the form of a hint vector. The hint reveals to D partial
information about the missingness of the original sample, which is used by D to
focus its attention on the imputation quality of particular components. This
hint ensures that G does in fact learn to generate according to the true data
distribution. We tested our method on various datasets and found that GAIN
significantly outperforms state-of-the-art imputation methods.

本文提出了一种新的通过使用生成对抗网络 (GAN) 框架来填补缺失数据的方法，称为生成对抗填补网络 (GAIN)。通过给 D 提供一些额外的信息，即提示向量，我们测试了我们的方法，并发现 GAIN 显著优于现有的插值方法。