# Tensor Completion with Provable Consistency and Fairness Guarantees for Recommender Systems

arXiv: https://arxiv.org/abs/2204.01815 · HTML: https://mlsanity.com/paper/2204.01815/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 63 references that are in the map.
- First posted on arXiv 4 Apr 2022.

## Builds on (most cited first, 11 of 11)

- [Explainable Recommendation: A Survey and New Perspectives](https://mlsanity.com/paper/1804.11192/) (2018)
- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Understanding Alternating Minimization for Matrix Completion](https://mlsanity.com/paper/1312.0925/) (2013)
- [A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion](https://mlsanity.com/paper/1309.6013/) (2013)
- [Matrix Completion via Max-Norm Constrained Optimization](https://mlsanity.com/paper/1303.0341/) (2013)
- [Exact tensor completion with sum-of-squares](https://mlsanity.com/paper/1702.06237/) (2017)
- [Low-Rank Tensor Completion by Truncated Nuclear Norm Regularization](https://mlsanity.com/paper/1712.00704/) (2017)
- [A Generalized Matrix Inverse with Applications to Robotic Systems](https://mlsanity.com/paper/1806.01776/) (2018)
- [A Scale-Consistent Approach for Recommender Systems](https://mlsanity.com/paper/1905.00055/) (2019)
- [On the Relative Gain Array (RGA) with Singular and Rectangular Matrices](https://mlsanity.com/paper/1805.10312/) (2018)

## Built on by (most cited first, 4 of 4)

- [A generalizable framework for low-rank tensor completion with numerical priors](https://mlsanity.com/paper/2302.05881/) (2023)
- [An Admissible Shift-Consistent Method for Recommender Systems](https://mlsanity.com/paper/2307.08857/) (2023)
- [Color Image Recovery Using Generalized Matrix Completion over Higher-Order Finite Dimensional Algebra](https://mlsanity.com/paper/2308.02621/) (2023)
- [Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan](https://mlsanity.com/paper/2408.05431/) (2024)

## Abstract (arXiv)

We introduce a new consistency-based approach for defining and solving nonnegative/positive matrix and tensor completion problems. The novelty of the framework is that instead of artificially making the problem well-posed in the form of an application-arbitrary optimization problem, e.g., minimizing a bulk structural measure such as rank or norm, we show that a single property/constraint: preserving unit-scale consistency, guarantees the existence of both a solution and, under relatively weak support assumptions, uniqueness. The framework and solution algorithms also generalize directly to tensors of arbitrary dimensions while maintaining computational complexity that is linear in problem size for fixed dimension d. In the context of recommender system (RS) applications, we prove that two reasonable properties that should be expected to hold for any solution to the RS problem are sufficient to permit uniqueness guarantees to be established within our framework. This is remarkable because it obviates the need for heuristic-based statistical or AI methods despite what appear to be distinctly human/subjective variables at the heart of the problem. Key theoretical contributions include a general unit-consistent tensor-completion framework with proofs of its properties, e.g., consensus-order and fairness, and algorithms with optimal runtime and space complexities, e.g., O(1) term-completion with preprocessing complexity that is linear in the number of known terms of the matrix/tensor. From a practical perspective, the seamless ability of the framework to generalize to exploit high-dimensional structural relationships among key state variables, e.g., user and product attributes, offers a means for extracting significantly more information than is possible for alternative methods that cannot generalize beyond direct user-product relationships.