Abstract
Tensor completion is a critical task in modern data science, yet traditional models like the Canonical Polyadic (CP) decomposition often fail in high-sparsity regimes. This paper investigates "quadratic tensors"—a model family based on pairwise interactions rather than triple products. We provide the first theoretical recovery guarantees for these models, proving that non-convex optimization techniques, such as Gradient Descent, can achieve perfect recovery with only a linear number of observations. Our findings demonstrate that quadratic tensors significantly outperform standard models in data-starved scenarios, offering a robust solution for sparse real-world applications.
Introduction
In the era of big data, the challenge is often not the volume of data, but its sparsity. Tensor completion—the process of predicting missing values in multi-dimensional arrays—is essential for applications ranging from recommendation systems to hyperspectral imaging. For example, in a 3D tensor representing Users, Movies, and Time, the vast majority of entries are empty because users interact with only a fraction of available content.
For decades, the CP decomposition has been the standard approach, modeling entries as the product of three vectors. However, CP models are notoriously data-hungry, typically requiring $O(d^{1.5})$ samples to reconstruct a $d$-dimensional tensor. In many practical settings, we only have access to $O(d)$ samples, leaving a significant gap between theoretical requirements and empirical reality. This paper bridges that gap by providing rigorous guarantees for quadratic tensors, which utilize pairwise interactions to achieve recovery with linear sample complexity.
The Quadratic Tensor Framework
Unlike the standard CP model, which relies on a triple-product form, quadratic models represent a 3D relationship as a sum of pairwise interactions (e.g., User-Movie + Movie-Time + User-Time). While these models have seen empirical success in recommendation engines, they previously lacked the theoretical foundations necessary to guarantee reliable recovery.
The authors analyze a non-convex least-squares formulation to learn these models. To ensure the optimization landscape is conducive to finding the global optimum, the methodology incorporates several key components:
- Over-parameterization: By searching in a space with a rank $R$ larger than the true rank $r$ (specifically $R \approx \sqrt{m}$, where $m$ is the sample count), the optimization landscape is smoothed, preventing the algorithm from stalling.
- Regularization and Incoherence: The objective function includes weight decay and an incoherence penalty. This ensures that information is distributed across the tensor rather than concentrated in a few entries, which is vital for recovery from random samples.
- Random Perturbation: The addition of a small, random positive semi-definite matrix to the objective acts as a smoothing agent, helping the solver avoid mathematically "flat" regions of the search space.
Theoretical Insights: No Bad Local Minima
The most significant theoretical contribution of this work is the discovery of the "No Bad Local Minima" phenomenon. The authors prove that for this specific quadratic formulation, all local minima are global minima. This implies that if a standard solver like Gradient Descent or Alternating Least Squares (ALS) stops descending, it has likely reached the correct solution rather than a suboptimal trap. This finding provides the mathematical justification for using efficient non-convex tools to solve what would otherwise be a daunting optimization problem.
Experimental Results
The researchers validated their theoretical claims through a series of experiments on synthetic and real-world datasets:
- Sample Complexity: Synthetic tests confirmed that quadratic models achieve ground-truth recovery once the number of samples reaches approximately $3 \times d \times r$, verifying the predicted linear scaling.
- MovieLens-10M: In predicting movie ratings where the third dimension was time intervals, the quadratic model outperformed CP decomposition by 10%, particularly when training data was limited to 20% of the total.
- Natural Language Processing: When learning word embeddings from a 1.5 billion-word Wikipedia corpus, the quadratic model showed a 20% improvement in accuracy over CP models on standard word analogy and similarity benchmarks.
- Hyperspectral Imaging: On extremely sparse data (0.1% observed), the quadratic model reduced error by more than half compared to the CP model, demonstrating its power in high-dimensional signal processing.
Conclusion and Trade-offs
While quadratic tensors offer superior performance in sparse regimes, they come with a representational trade-off. Because they are a restricted subset of general tensors, they are less "expressive" than CP models. In scenarios where data is abundant (e.g., 10% or more of a hyperspectral image is observed), the more flexible CP model eventually overtakes the quadratic model in accuracy.
In summary, quadratic tensors are a powerful tool for sparse data recovery, offering linear sample complexity and guaranteed convergence to global optima. Future work will focus on refining convergence rates and exploring whether the over-parameterization requirements can be further reduced to scale solely with the true rank of the tensor.
Summary updated