TL;DR
This paper introduces new, practical algorithms for finding low-rank approximations of matrices using $l_p$-norms (specifically $l_1$ and $l_\infty$), which are more robust to outliers than the standard $l_2$-norm. Their approach, based on smooth approximations and gradient descent, achieves competitive or better performance than existing methods, offering a more robust and often faster alternative for real-world applications.
What Problem Does This Paper Address?
Low-rank approximation is a fundamental technique in data analysis, used for tasks like dimensionality reduction, noise reduction, and recommender systems. The standard approach uses the $l_2$-norm (Frobenius norm), which has a convenient closed-form solution via Singular Value Decomposition (SVD). However, the $l_2$-norm is sensitive to outliers in the data. The $l_1$ and $l_\infty$ norms are more robust to outliers, making them suitable for real-world scenarios where data can be noisy or contain anomalies. The challenge is that finding low-rank approximations with $l_1$ or $l_\infty$ norms is computationally much harder (NP-hard) and lacks a simple closed-form solution. Existing methods for these norms are either theoretically complex, computationally expensive, or lack rigorous guarantees. This paper aims to bridge this gap by providing practical, provably good algorithms for $l_1$ and $l_\infty$ low-rank approximation.
Methods
The core of the proposed method lies in transforming the non-smooth $l_1$ and $l_\infty$ norms into smooth, differentiable approximations. For the $l_1$-norm, they use the Charbonnier loss function, and for the $l_\infty$-norm, they employ the log-sum-exp function. These smooth approximations allow them to leverage powerful gradient-based optimization techniques.
Specifically, they adapt the Bi-Factored Gradient Descent (BFGD) algorithm, a non-convex gradient descent method for smooth objectives, to work with these smoothed $l_p$-norm objectives. To ensure convergence and achieve theoretical guarantees, they also add a strongly convex regularizer to the objective function. This modification turns the problem into one that can be solved efficiently with provable guarantees, even though the original problem is non-convex.
The algorithms require knowledge of certain problem-specific quantities (like the optimal objective value and properties of the optimal solution) to set their hyperparameters. However, the authors emphasize that these quantities only need to be approximated, making the algorithms practical.
Datasets
The paper evaluates their algorithms on both synthetic and real-world datasets.
- Synthetic Datasets:
- Random matrices with entries drawn from a uniform distribution in [0,1].
- Random matrices with entries drawn from {±1} with equal probability.
- Matrices generated as $M = UV^T$, where $U$ and $V$ have entries drawn from a standard normal distribution, and then rounded to create a low-rank structure with a known bound on the $l_\infty$ error.
- Real-World Datasets:
- FIDAP dataset (a word frequency dataset).
- A word frequency dataset from UCI.
The authors note that for the large word frequency dataset, one of the compared methods (from [9]) could not complete the task due to scalability issues.
Key Insights and Ideas
- Smooth Approximations are Key: The paper demonstrates that by cleverly smoothing the non-convex $l_1$ and $l_\infty$ norms, one can unlock the power of gradient-based optimization for these challenging problems.
- Bridging Theory and Practice: While the problem is NP-hard, the authors show that with approximations of certain problem quantities, one can achieve provable $(1+\epsilon)$-OPT approximations in polynomial time. This is a significant theoretical result with practical implications.
- Robustness Matters: The motivation for using $l_1$ and $l_\infty$ norms is their robustness to outliers, which is crucial in many real-world applications where data is imperfect. This work provides a practical way to leverage this robustness.
- BFGD as a Versatile Sub-solver: The paper highlights the effectiveness of the Bi-Factored Gradient Descent (BFGD) algorithm as a general-purpose solver for non-convex matrix factorization problems, even when applied to smoothed objectives.
Key Results
- Theoretical Guarantees: The proposed algorithms achieve $(1+\epsilon)$-OPT approximations for $l_1$ and $l_\infty$ low-rank approximation problems.
- Empirical Performance:
- On synthetic datasets, their approach often achieves better objective function values and is faster than existing heuristic methods ([9]).
- On real-world datasets, their method is competitive and often outperforms other approaches in terms of objective function quality.
- For the $l_\infty$-norm, their method's median objective values are lower than a compared heuristic ([17]), indicating better typical performance.
- Scalability: While their method is generally slower than plain SVD (which provides a suboptimal solution), it scales better than some existing methods for $l_p$-norms, especially for large matrices.
Limitations and Future Work
- Hyperparameter Dependence: The algorithms require knowledge or approximation of certain problem-specific quantities (optimal objective value, properties of the optimal solution). While the authors argue these can be approximated, it's a practical consideration.
- Computational Cost: While practical and often faster than some alternatives, the proposed methods are still slower than the SVD-based $l_2$-norm approximation. Accelerating their algorithm is identified as a future research direction.
- Weighted Low-Rank Approximation: A significant open problem highlighted is extending their work to weighted low-rank approximation, where different weights are applied to different entries of the matrix.
- Non-asymptotic Convergence: The current theoretical guarantees are asymptotic; exploring non-asymptotic convergence results is also suggested.
Summary updated