TL;DR
This paper introduces a new algorithm, CPAL1, for tensor factorization that is robust to non-Gaussian noise, a common issue in real-world data. By using an L1-norm objective function instead of the standard L2-norm (least squares), CPAL1 can better handle "artifact noise" – sparse, high-intensity outliers that can significantly skew results from traditional methods.
What Problem Does This Paper Address?
Tensor factorization, specifically the CANDECOMP/PARAFAC (CP) model, is a powerful tool for analyzing multi-way data across various fields. The standard method for fitting CP models relies on a least-squares objective function. While this is optimal for data corrupted by independent and identically distributed (i.i.d.) Gaussian noise, it's highly susceptible to outliers or "artifact noise." This type of noise, characterized by sparse but significant deviations from the norm (e.g., movement artifacts in fMRI data or foreground objects in video), can severely degrade the accuracy of the factorization. The paper aims to develop a CP factorization method that is less sensitive to these non-Gaussian perturbations.
Methods
The core of the paper's contribution lies in two main areas:
- Robust Loss Function: Instead of the standard L2-norm (Frobenius norm) loss, the authors propose using an L1-norm objective function. The L1-norm is known for its robustness to outliers. To make this optimization tractable, they introduce a smoothed and regularized version of the L1-norm loss, denoted as $L_{\epsilon,\mu}(u)$.
- Majorization-Minimization (MM) Algorithm: To efficiently minimize the proposed robust loss function for CP factorization, they develop an alternating majorization-minimization (MM) algorithm. This algorithm iteratively updates each factor matrix (A, B, C) while holding the others fixed. The key insight is that the subproblem for updating each factor matrix can be framed as a series of independent L1-regression problems, which are then solved using the MM approach. This is termed CPAL1 (CP Alternating L1).
Datasets
The paper does not introduce new datasets. Instead, it uses simulated data for evaluation. The authors generate 3-way tensors of size $50 \times 50 \times 50$ with a rank of 5. To these "clean" tensors, they add two types of noise:
- Dense Gaussian Noise: i.i.d. draws from a standard Gaussian distribution.
- Artifact Outliers: A fraction of tensor entries are randomly selected and perturbed with values drawn from a Gamma distribution, while other entries are set to zero.
The parameters for the artifact noise ($\eta$, the fraction of affected entries) and its intensity ($\gamma$) are varied to simulate different scenarios of non-Gaussian perturbations.
Key Insights and Ideas
- L2-norm's Achilles' Heel: The standard least-squares (L2-norm) approach for CP factorization, while mathematically convenient, is surprisingly brittle when faced with non-Gaussian noise, especially sparse, high-magnitude outliers.
- L1-norm as a Shield: The L1-norm objective function offers a principled way to achieve robustness against these outliers. It down-weights the influence of extreme values compared to the L2-norm.
- MM for Tractability: Directly minimizing the L1-norm can be challenging due to its non-differentiability. The MM algorithm provides an effective framework to iteratively approximate and minimize a smoothed version of the L1-norm loss, making the optimization practical.
- Parallelizable Updates: A significant advantage of the proposed MM approach is that the update for each factor matrix decomposes into many small, independent L1-regression problems. This structure opens up opportunities for significant speedups through parallelization, especially for large tensors.
Key Results
The paper presents simulation results comparing their proposed CPAL1 algorithm against the standard CP Alternating Least Squares (CPALS) method.
- Robustness to Artifact Noise: Figure 1a clearly shows that as the intensity and proportion of artifact noise ($\eta$ and $\gamma$) increase, the Factor Match Score (FMS) for CPALS degrades significantly. In contrast, CPAL1 maintains a much higher FMS, demonstrating its robustness.
- Performance Comparison: While CPAL1 generally outperforms CPALS in the presence of artifact noise, it occasionally gets stuck in local minima. However, even in these cases, its performance is often comparable to or better than CPALS.
- Qualitative Example: Figure 1b provides a visual comparison of a recovered factor column. The CPAL1 result is a much better match to the true factor column than the CPALS result, highlighting the practical impact of the robustness. The FMS for this specific replicate was 0.91 for CPAL1 versus 0.64 for CPALS.
- Speed: The authors mention that their method performed slightly faster on tensors of similar size to those tested, and they suspect the performance gap will widen with larger tensors due to parallelization opportunities.
Limitations and Future Work
- Data Density: The authors conjecture that CPAL1 is most suited for handling artifact noise when the data tensor is dense. They note that CPAL1 can struggle as much as CPALS when the data tensor is sparse.
- Future Research Directions:
- Finding an alternative to the L1-norm loss for sparse data with non-Gaussian noise is identified as a key area for future research.
- Exploring further speed-up opportunities through parallelization is also suggested.
Summary updated