Weighted low rank approximation (WLRA) is an important yet computationally
challenging primitive with applications ranging from statistical analysis,
model compression, and signal processing. To cope with the NP-hardness of this
problem, prior work considers heuristics, bicriteria, or fixed parameter
tractable algorithms to solve this problem. In this work, we introduce a new
relaxed solution to WLRA which outputs a matrix that is not necessarily low
rank, but can be stored using very few parameters and gives provable
approximation guarantees when the weight matrix has low rank. Our central idea
is to use the weight matrix itself to reweight a low rank solution, which gives
an extremely simple algorithm with remarkable empirical performance in
applications to model compression and on synthetic datasets. Our algorithm also
gives nearly optimal communication complexity bounds for a natural distributed
problem associated with this problem, for which we show matching communication
lower bounds. Together, our communication complexity bounds show that the rank
of the weight matrix provably parameterizes the communication complexity of
WLRA. We also obtain the first relative error guarantees for feature selection
with a weighted objective.

通过使用权重矩阵本身进行矩阵重新加权，我们提出了一种放松的 WLRA 解法，该方法可以输出一个并非低秩矩阵，但可以使用非常少的参数进行存储，并在权重矩阵具有低秩时给出可证明的近似保证。此外，我们的算法在模型压缩和合成数据集方面展现出非常出色的实证性能，并为与此问题相关的自然分布问题提供了几乎最佳的通信复杂性界限。

加权低秩逼近的重新加权解

Reweighted Solutions for Weighted Low Rank Approximation

Weighted low rank approximation is a fundamental problem in numerical linear
algebra, and it has many applications in machine learning. Given a matrix $M
\in \mathbb{R}^{n \times n}$, a weight matrix $W \in \mathbb{R}_{\geq 0}^{n
\times n}$, a parameter $k$, the goal is to output two matrices $U, V \in
\mathbb{R}^{n \times k}$ such that $\| W \circ (M - U V) \|_F$ is minimized,
where $\circ$ denotes the Hadamard product. Such a problem is known to be
NP-hard and even hard to approximate [RSW16]. Meanwhile, alternating
minimization is a good heuristic solution for approximating weighted low rank
approximation. The work [LLR16] shows that, under mild assumptions, alternating
minimization does provide provable guarantees. In this work, we develop an
efficient and robust framework for alternating minimization. For weighted low
rank approximation, this improves the runtime of [LLR16] from $n^2 k^2$ to
$n^2k$. At the heart of our work framework is a high-accuracy multiple response
regression solver together with a robust analysis of alternating minimization.

本研究提供了一种有效和稳健的交替最小化框架来解决线性代数和机器学习中的一些问题，关注于都市中加权矩阵的低秩矩阵近似问题，并将运行时间从之前的 n^2k^2 降至 n^2k。