# Nonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank Approximation

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 99 references that are in the map.
- First posted on arXiv 19 May 2023.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Tensor Ring Decomposition](https://mlsanity.com/paper/1606.05535/) (2016)
- [Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm](https://mlsanity.com/paper/1804.03728/) (2018)
- [Exact tensor completion using t-SVD](https://mlsanity.com/paper/1502.04689/) (2015)
- [Efficient tensor completion for color image and video recovery: Low-rank tensor train](https://mlsanity.com/paper/1606.01500/) (2016)
- [Guaranteed Tensor Recovery Fused Low-rankness and Smoothness](https://mlsanity.com/paper/2302.02155/) (2023)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Robust Low-rank Tensor Recovery: Models and Algorithms](https://mlsanity.com/paper/1311.6182/) (2013)
- [Bayesian Robust Tensor Factorization for Incomplete Multiway Data](https://mlsanity.com/paper/1410.2386/) (2014)
- [Fast and Guaranteed Tensor Decomposition via Sketching](https://mlsanity.com/paper/1506.04448/) (2015)
- [Tensor N-tubal rank and its convex relaxation for low-rank tensor recovery](https://mlsanity.com/paper/1812.00688/) (2018)
- [Noisy Tensor Completion via Low-rank Tensor Ring](https://mlsanity.com/paper/2203.08857/) (2022)
- [Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction](https://mlsanity.com/paper/1901.01652/) (2019)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [Single-Pass PCA of Large High-Dimensional Data](https://mlsanity.com/paper/1704.07669/) (2017)
- [Robust Low-tubal-rank Tensor Completion based on Tensor Factorization and Maximum Correntopy Criterion](https://mlsanity.com/paper/2010.11740/) (2020)
- [Randomized Algorithms for Scientific Computing (RASC)](https://mlsanity.com/paper/2104.11079/) (2021)
- [Coarse to Fine Two-Stage Approach to Robust Tensor Completion of Visual Data](https://mlsanity.com/paper/2106.10422/) (2021)

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

- [NeSyCoCo: A Neuro-Symbolic Concept Composer for Compositional Generalization](https://mlsanity.com/paper/2412.15588/) (2024)
- [A Survey on Inference Engines for Large Language Models: Perspectives on Optimization and Efficiency](https://mlsanity.com/paper/2505.01658/) (2025)
- [LoRA-PT: Low-Rank Adapting UNETR for Hippocampus Segmentation Using Principal Tensor Singular Values and Vectors](https://mlsanity.com/paper/2407.11292/) (2024)
- [Hyperspectral Anomaly Detection Fused Unified Nonconvex Tensor Ring Factors Regularization](https://mlsanity.com/paper/2505.17881/) (2025)
- [Beyond Motion Cues and Structural Sparsity: Revisiting Small Moving Target Detection](https://mlsanity.com/paper/2509.07654/) (2025)
- [Robust Low-Rank Tensor Completion based on M-product with Weighted Correlated Total Variation and Sparse Regularization](https://mlsanity.com/paper/2604.13525/) (2026)
- [Semi-Tensor Product-Based Multi-Term Randomized T-SVD and Its Visual Applications](https://mlsanity.com/paper/2609.11168/) (2026)

## Abstract (arXiv)

Within the tensor singular value decomposition (T-SVD) framework, existing robust low-rank tensor completion approaches have made great achievements in various areas of science and engineering. Nevertheless, these methods involve the T-SVD based low-rank approximation, which suffers from high computational costs when dealing with large-scale tensor data. Moreover, most of them are only applicable to third-order tensors. Against these issues, in this article, two efficient low-rank tensor approximation approaches fusing randomized techniques are first devised under the order-d (d >= 3) T-SVD framework. On this basis, we then further investigate the robust high-order tensor completion (RHTC) problem, in which a double nonconvex model along with its corresponding fast optimization algorithms with convergence guarantees are developed. To the best of our knowledge, this is the first study to incorporate the randomized low-rank approximation into the RHTC problem. Empirical studies on large-scale synthetic and real tensor data illustrate that the proposed method outperforms other state-of-the-art approaches in terms of both computational efficiency and estimated precision.