Fast Tensor Completion via Approximate Richardson Iteration
We study tensor completion (TC) through the lens of low-rank tensor decomposition (TD). Many TD algorithms use fast alternating minimization methods, which solve highly structured linear regression problems at each step (e.g., for CP, Tucker, and tensor-train decompositions). However, such algebraic structure is lost in TC regression problems, making direct extensions unclear. To address this, we propose a lifting approach that approximately solves TC regression problems using structured TD regression algorithms as blackbox subroutines, enabling sublinear-time methods. We theoretically analyze the convergence rate of our approximate Richardson iteration based algorithm, and we demonstrate on real-world tensors that its running time can be 100x faster than direct methods for CP completion.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionTensor DecompositionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Transformers Can Implement Preconditioned Richardson Iteration for In-Context Gaussian Kernel Regression
Mechanistic accounts of in-context learning (ICL) have identified iterative algorithms for linear regression and related linear prediction tasks, often using linear or ReLU attention variants. For nonlinear ICL, prior wo…
Fast and Provable Tensor-Train Format Tensor Completion via Precondtioned Riemannian Gradient Descent
Low-rank tensor completion aims to recover a tensor from partially observed entries, and it is widely applicable in fields such as quantum computing and image processing. Due to the significant advantages of the tensor t…
Quantum State TomographyGeneralized Higher-Order Orthogonal Iteration for Tensor Decomposition and Completion
Low-rank tensor estimation has been frequently applied in many real-world problems. Despite successful applications, existing Schatten 1-norm minimization (SNM) methods may become very slow or even not applicable for lar…
Tensor DecompositionDONE: Distributed Approximate Newton-type Method for Federated Edge Learning
There is growing interest in applying distributed machine learning to edge computing, forming federated edge learning. Federated edge learning faces non-i.i.d. and heterogeneous data, and the communication between edge w…
Edge-computingVocal Bursts Type PredictionLow-tubal-rank Tensor Completion using Alternating Minimization
The low-tubal-rank tensor model has been recently proposed for real-world multidimensional data. In this paper, we study the low-tubal-rank tensor completion problem, i.e., to recover a third-order tensor by observing a …
2kLow-Rank Matrix CompletionMatrix Completion