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