Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent

• URL: http://arxiv.org/abs/2512.07490v2
• Date: Mon, 15 Dec 2025 09:28:22 GMT
• Title: Efficient Low-Tubal-Rank Tensor Estimation via Alternating Preconditioned Gradient Descent
• Authors: Zhiyu Liu, Zhi Han, Yandong Tang, Jun Fan, Yao Wang,
• Abstract summary: Low-tubal-rank tensor estimation is a fundamental task with wide applications across high-dimensional signal processing, machine learning, and image science.<n>Recent approaches address this issue by factorizing the tensor into two smaller factor tensors and solving the resulting problem using gradient descent.<n>We propose an Alternating Preconditioned Gradient Descent (APGD) algorithm, which accelerates convergence in the over- parameterized setting.
• Score: 16.904277250824055
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of low-tubal-rank tensor estimation is a fundamental task with wide applications across high-dimensional signal processing, machine learning, and image science. Traditional approaches tackle such a problem by performing tensor singular value decomposition, which is computationally expensive and becomes infeasible for large-scale tensors. Recent approaches address this issue by factorizing the tensor into two smaller factor tensors and solving the resulting problem using gradient descent. However, this kind of approach requires an accurate estimate of the tensor rank, and when the rank is overestimated, the convergence of gradient descent and its variants slows down significantly or even diverges. To address this problem, we propose an Alternating Preconditioned Gradient Descent (APGD) algorithm, which accelerates convergence in the over-parameterized setting by adding a preconditioning term to the original gradient and updating these two factors alternately. Based on certain geometric assumptions on the objective function, we establish linear convergence guarantees for more general low-tubal-rank tensor estimation problems. Then we further analyze the specific cases of low-tubal-rank tensor factorization and low-tubal-rank tensor recovery. Our theoretical results show that APGD achieves linear convergence even under over-parameterization, and the convergence rate is independent of the tensor condition number. Extensive simulations on synthetic data are carried out to validate our theoretical assertions.

Related papers

• Improved Convergence in Parameter-Agnostic Error Feedback through Momentum [49.163769734936295]
  We study normalized error feedback algorithms that combine EF with normalized updates, various momentum variants, and parameter-agnostic, time-varying stepsizes.<n>Our results hold with decreasing stepsizes and small mini-batches.
  arXiv  Detail & Related papers  (2025-11-18T13:47:08Z)
• Score-Based Model for Low-Rank Tensor Recovery [49.158601255093416]
  Low-rank tensor decompositions (TDs) provide an effective framework for multiway data analysis.<n>Traditional TD methods rely on predefined structural assumptions, such as CP or Tucker decompositions.<n>We propose a score-based model that eliminates the need for predefined structural or distributional assumptions.
  arXiv  Detail & Related papers  (2025-06-27T15:05:37Z)
• Low-Rank Tensor Recovery via Variational Schatten-p Quasi-Norm and Jacobian Regularization [49.85875869048434]
  We propose a CP-based low-rank tensor function parameterized by neural networks for implicit neural representation.<n>To achieve sparser CP decomposition, we introduce a variational Schatten-p quasi-norm to prune redundant rank-1 components.<n>For smoothness, we propose a regularization term based on the spectral norm of the Jacobian and Hutchinson's trace estimator.
  arXiv  Detail & Related papers  (2025-06-27T11:23:10Z)
• A Scalable Factorization Approach for High-Order Structured Tensor Recovery [30.876260188209105]
  decompositions, which represent an $N$-order tensor using approximately $N$ factors of much smaller dimensions, can significantly reduce the number of parameters.<n>A computationally memory-efficient approach to these problems is to optimize directly over factors using local algorithms.<n>We present a unified framework for factorization approach to solving various tensor decomposition problems.
  arXiv  Detail & Related papers  (2025-06-19T05:07:07Z)
• Guaranteed Nonconvex Low-Rank Tensor Estimation via Scaled Gradient Descent [4.123899820318987]
  This paper develops a scaled gradient descent (ScaledGD) algorithm to directly estimate the tensor factors.<n>In theory, ScaledGD achieves linear convergence at a constant rate that is independent of the condition number of the ground truth low-rank tensor.<n> numerical examples are provided to demonstrate the efficacy of ScaledGD in accelerating the convergence rate of ill-conditioned low-rank tensor estimation.
  arXiv  Detail & Related papers  (2025-01-03T08:26:01Z)
• Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent [21.51873526389341]
  We propose an efficient and effective low-tubal-rank tensor recovery method based on a factorization procedure akin to the Burer-Monteiro method.<n>We provide rigorous theoretical analysis to ensure the convergence of FGD under both noise-free and noisy situations.<n>Our approach exhibits superior performance in multiple scenarios, in terms of the faster computational speed and the smaller convergence error.
  arXiv  Detail & Related papers  (2024-01-22T13:30:11Z)
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization [48.65416821017865]
  This chapter introduces a new algorithmic approach, dubbed scaled gradient (ScaledGD) It converges linearly at a constant rate independent of the condition number of the low-rank object. It maintains the low periteration cost of gradient descent for a variety of tasks.
  arXiv  Detail & Related papers  (2023-10-09T21:16:57Z)
• Error Analysis of Tensor-Train Cross Approximation [88.83467216606778]
  We provide accuracy guarantees in terms of the entire tensor for both exact and noisy measurements. Results are verified by numerical experiments, and may have important implications for the usefulness of cross approximations for high-order tensors.
  arXiv  Detail & Related papers  (2022-07-09T19:33:59Z)
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements [30.395874385570007]
  A fundamental task is to faithfully recover tensors from highly incomplete measurements. We develop an algorithm to directly recover the tensor factors in the Tucker decomposition. We show that it provably converges at a linear independent rate of the ground truth tensor for two canonical problems.
  arXiv  Detail & Related papers  (2021-04-29T17:44:49Z)
• Uncertainty quantification for nonconvex tensor completion: Confidence intervals, heteroscedasticity and optimality [92.35257908210316]
  We study the problem of estimating a low-rank tensor given incomplete and corrupted observations. We find that it attains unimprovable rates $ell-2$ accuracy.
  arXiv  Detail & Related papers  (2020-06-15T17:47:13Z)
• Tensor denoising and completion based on ordinal observations [11.193504036335503]
  We consider the problem of low-rank tensor estimation from possibly incomplete, ordinal-valued observations. We propose a multi-linear cumulative link model, develop a rank-constrained M-estimator, and obtain theoretical accuracy guarantees. We show that the proposed estimator is minimax optimal under the class of low-rank models.
  arXiv  Detail & Related papers  (2020-02-16T07:09:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.