Simple and practical algorithms for 𝓁p-norm low-rank approximation

Anastasios Kyrillidis

TL;DR

This paper introduces novel, practical, and theoretically-backed algorithms for $\ell_p$-norm low-rank approximation, specifically for $p=1$ and $p=\infty$. These algorithms, based on a smooth, non-convex, gradient-based approach, achieve $(1+\varepsilon)$-OPT approximations and outperform existing state-of-the-art methods in practice, offering a faster and more accurate solution to a challenging problem.

What Problem Does This Paper Address?

The paper tackles the problem of finding the best rank-$r$ approximation of a given matrix $M$ with respect to the entrywise $\ell_p$-norm, mathematically formulated as minimizing $||M - UV^T||_p$ where $U$ and $V$ are matrices of rank $r$. While the $\ell_2$-norm (Frobenius norm) low-rank approximation has a well-known closed-form solution via Singular Value Decomposition (SVD), the $\ell_1$ and $\ell_\infty$ norms are significantly harder to optimize. Finding exact solutions for these norms is proven to be computationally intractable (NP-hard), and existing approximation algorithms often rely on complex techniques or lack strong theoretical guarantees. This paper aims to bridge this gap by proposing practical, efficient, and theoretically sound algorithms for these important $\ell_p$-norm variants.

Methods

The core of the proposed approach lies in transforming the non-smooth $\ell_p$-norm objective functions ($p=1, \infty$) into smooth, convex, and differentiable approximations. This is achieved using:

  • Charbonnier Loss Function: For the $\ell_1$-norm, the paper employs the Charbonnier loss function, which is a smooth approximation that ensures Lipschitz continuous gradients.
  • Logsumexp Function: For the $\ell_\infty$-norm, the logsumexp function is used as a smooth surrogate.

These smoothed objectives are then optimized using a Bi-Factored Gradient Descent (BFGD) algorithm, a non-convex gradient descent method that operates on the factorized form $UV^T$. The BFGD algorithm is adapted to handle the smoothed objectives and is further regularized with a strongly convex component to ensure good initialization and convergence properties. The theoretical analysis relies on bounding the objective function using its smoothed counterpart and leveraging the provable performance of the non-convex algorithm. The algorithms require knowledge of certain problem quantities (like the optimal function value and properties of the optimal solution) which, importantly, only need to be approximated for the theoretical guarantees to hold.

Datasets

The paper evaluates its algorithms on both synthetic and real-world datasets.

  • Synthetic Datasets:
    • $20 \times 30$ matrices with entries drawn uniformly from $[0,1]$.
  • $20 \times 30$ matrices with entries drawn from $\{\pm 1\}$ with equal probability.
  • Matrices generated as $M = UV^T$ where $U \in \mathbb{R}^{100 \times r}$ and $V \in \mathbb{R}^{75 \times r}$, with entries of $U$ and $V$ drawn i.i.d. from $\mathcal{N}(0,1)$, and then rounded to create a low-rank structure with bounded error.
  • Real-World Datasets:
    • FIDAP dataset: A $27 \times 27$ matrix with asymmetric non-zero entries.
  • Word frequency dataset (UCI): A large $3430 \times 6906$ matrix.

The synthetic data generation for the $\ell_\infty$ norm is specifically designed to create a low-rank matrix with a bounded error, mimicking a scenario where the true low-rank structure is perturbed.

Key Insights and Ideas

  • Smooth Approximations for Non-Smooth Norms: The core insight is that by using well-chosen smooth approximations (Charbonnier and logsumexp), the intractable $\ell_1$ and $\ell_\infty$ low-rank approximation problems can be tackled with gradient-based methods, which are generally easier to implement and analyze.
  • Bridging Theory and Practice: The paper successfully connects theoretical guarantees of $(1+\varepsilon)$-OPT approximations with practical algorithmic implementations, demonstrating that these complex theoretical results can lead to effective real-world solutions.
  • The Importance of Approximable Hyperparameters: A key theoretical finding is that the algorithms achieve their guarantees not by knowing exact values of certain problem quantities (like the optimal objective value), but by assuming these quantities are approximable. This is a crucial practical consideration, as exact values are often unknown.
  • BFGD as a Versatile Sub-Solver: The paper highlights the utility of the Bi-Factored Gradient Descent (BFGD) algorithm as a robust sub-solver for smooth, non-convex matrix factorization problems, adaptable to different objectives.

Key Results

  • Theoretical Guarantees: The proposed algorithms achieve $(1+\varepsilon)$-OPT approximations for both $\ell_1$ and $\ell_\infty$ low-rank approximation problems.
  • Practical Performance: Experiments show that the proposed algorithms are competitive with, and often outperform, state-of-the-art methods in terms of both objective function value and execution time, especially for larger problems.
  • Speed and Accuracy: For synthetic datasets, the proposed method consistently achieves better objective function values faster than existing methods. For real datasets, it generally offers superior objective function values, though sometimes at a higher computational cost compared to simpler heuristics.
  • Scalability: The paper notes that for very large matrices, some existing methods struggle to scale, whereas their proposed approach shows more promise.

Limitations and Future Work

  • Hyperparameter Dependence: The algorithms are not hyperparameter-free. While the theory shows that approximations of certain quantities are sufficient, these approximations still need to be determined. The paper acknowledges that finding good hyperparameters is crucial.
  • Computational Cost: While competitive, the proposed algorithms can be slower than simpler methods like SVD or some heuristics, particularly for the $\ell_\infty$ case. Accelerating the algorithm is identified as a direction for future research.
  • Weighted Low-Rank Approximation: The paper suggests extending the approach to handle weighted low-rank matrix approximation as a particularly interesting open problem.
  • Missing Data: The authors note that some existing heuristics are designed to handle missing data, a feature not directly addressed in this work but considered for future research.
  • Initialization: While the theory relies on good initialization, the paper's experiments show that standard SVD-based initialization works well in practice, even if theoretical conditions are not strictly met.

Summary updated

Abstract

We propose practical algorithms for entrywise $\ell_p$-norm low-rank approximation, for $p = 1$ or $p = \infty$. The proposed framework, which is non-convex and gradient-based, is easy to implement and typically attains better approximations, faster, than state of the art. From a theoretical standpoint, we show that the proposed scheme can attain $(1 + \varepsilon)$-OPT approximations. Our algorithms are not hyperparameter-free: they achieve the desiderata only assuming algorithm's hyperparameters are known a priori---or are at least approximable. I.e., our theory indicates what problem quantities need to be known, in order to get a good solution within polynomial time, and does not contradict to recent inapproximabilty results, as in [46].
BibTeX
@inproceedings{kyrillidis2018simple,
  author = {Anastasios Kyrillidis},
  title = {{Simple and practical algorithms for 𝓁p-norm low-rank approximation}},
  booktitle = {UAI},
  year = {2018},
  url = {https://openreview.net/forum?id=rhtgY5GjXTG},
}
Figure