  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.
