Source-linked AI summary
Tensor Ring Decomposition with Rank Minimization on Latent Space: An Efficient Approach for Tensor Completion
Longhao Yuan, Chao Li, Danilo Mandic, Jianting Cao, Qibin Zhao
TL;DR
Traditional tensor completion struggles with rank selection in tensor decompositions and with costly large-scale SVDs in rank-minimization methods. The paper proposes TRLRF, which regularizes latent TR factors with nuclear norms and uses ADMM to obtain factors and the recovered tensor simultaneously. Experiments on synthetic and real-world data show superior performance and efficiency against state-of-the-art algorithms.
Problem
Traditional tensor completion methods face high sensitivity to rank selection, while nuclear-norm approaches require costly large-scale SVD operations.
Method
TRLRF imposes nuclear norm regularization on latent TR factors and uses ADMM to optimize the factors and recovered tensor simultaneously.
Results
Extensive experiments on synthetic and real-world data demonstrate that TRLRF outperforms state-of-the-art algorithms.
Takeaways & Limitations
TRLRF alleviates TR-rank selection and reduces computational cost while providing an efficient tensor completion method.
Abstract
from arXiv · showhide
In tensor completion tasks, the traditional low-rank tensor decomposition models suffer from the laborious model selection problem due to their high model sensitivity. In particular, for tensor ring (TR) decomposition, the number of model possibilities grows exponentially with the tensor order, which makes it rather challenging to find the optimal TR decomposition. In this paper, by exploiting the low-rank structure of the TR latent space, we propose a novel tensor completion method which is robust to model selection. In contrast to imposing the low-rank constraint on the data space, we introduce nuclear norm regularization on the latent TR factors, resulting in the optimization step using singular value decomposition (SVD) being performed at a much smaller scale. By leveraging the alternating direction method of multipliers (ADMM) scheme, the latent TR factors with optimal rank and the recovered tensor can be obtained simultaneously. Our proposed algorithm is shown to effectively alleviate the burden of TR-rank selection, thereby greatly reducing the computational cost. The extensive experimental results on both synthetic and real-world data demonstrate the superior performance and efficiency of the proposed approach against the state-of-the-art algorithms.
Introduction
Tensor completion methods use low-rank structure to recover missing entries, but traditional tensor decompositions are highly sensitive to rank selection and rank-minimization methods can be computationally costly. TRLRF addresses both issues by regularizing low-rank TR factors and solving decomposition and completion simultaneously with ADMM.
- Tensor completion recovers incomplete tensors from partially observed entries using low-rank structure, with decomposition-based and rank-minimization-based approaches.
- Traditional decomposition methods use latent factors to predict missing entries, but their performance is sensitive to selecting data-dependent tensor ranks.For Tucker, TT, and TR decompositions, rank is a vector with immense possibilities, making cross-validation impractical.
- Rank-minimization methods avoid prespecifying rank but incur high computational cost from multiple large-scale SVD operations and hyper-parameter tuning.Nuclear norm regularization automatically learns rank from limited observations, while SVDs on tensor unfoldings reduce efficiency.
- TRLRF reduces rank-selection sensitivity and computational cost by imposing nuclear norm regularization on latent TR factors rather than directly on the data tensor.The approach combines tensor decomposition and nuclear norm regularization to provide performance stability and computational efficiency.
- A theoretical relationship between multilinear tensor rank and TR-factor rank enables low-rank constraints and SVD calculations on smaller latent factors.
- Nuclear-norm regularized TR ranks yield stable solutions even when the initial TR rank is inappropriate, while ADMM obtains TR factors and the recovered tensor simultaneously.
Preliminaries and Related Works
Tensor decomposition represents incomplete data through latent factors, while TR provides a flexible circular factorization that scales linearly with tensor order. Related completion methods either rely on rank-sensitive TR optimization or nuclear-norm regularization whose large-scale SVD operations become expensive.
- Tensor notation includes scalars, vectors, matrices, higher-order tensors, tensor sequences, tensor inner products, Frobenius norms, and mode-n unfolding operators.The paper distinguishes standard mode-n unfolding from the TR-oriented unfolding X<n> and defines matrix folding as the inverse operation.
- Tensor ring decomposition: TR decomposition represents a higher-order tensor through circular multilinear products of third-order latent core tensors called TR factors.Each factor has two rank modes and one dimension mode, and the TR-rank vector controls model complexity.
- Tensor ring decomposition: TR generalizes tensor-train decomposition by equating the first and last TT ranks, while offering representation ability that scales linearly with tensor order.
- Completion by TR decomposition: TR completion methods use observed entries to optimize TR factors whose generated tensor predicts the missing entries.TRALS uses alternating least squares, whereas TRWOPT uses a gradient-based algorithm on the same optimization model.
- Completion by TR decomposition: TRALS and TRWOPT perform well across tensor orders but suffer from high sensitivity to TR-rank selection, increasing computational cost.
- Completion by nuclear norm regularization: Rank-minimization completion formulates recovery around a low-rank tensor and replaces rank regularization with nuclear norms based on sums of matrix singular values.
- Completion by nuclear norm regularization: Nuclear-norm completion is commonly solved with ADMM, but repeated SVD operations become intractable on large-scale data because of their computational cost.
Tensor Ring Low-rank Factors
TRLRF places low-rank constraints on TR factors, using a tensor-rank relationship to avoid direct data-space regularization. ADMM jointly updates the recovered tensor and factors, while factor-scale SVDs reduce computational cost and improve rank-selection robustness.
- Model formulation: TRLRF imposes low-rankness on each TR factor rather than directly on the original tensor.The model uses nuclear norm regularization on factor unfoldings.
- Rank relationship: Theorem 1 establishes that each tensor mode-n unfolding rank is upper bounded by the corresponding TR-factor unfolding rank.This relationship permits low-rank constraints to be imposed on TR factors.
- Rank robustness: Regularizing dimension-mode and rank-mode factor unfoldings makes the initial TR-rank an upper bound on the tensor's real TR-rank.The fitting error and nuclear norms are minimized simultaneously, providing robustness to rank selection.
- Optimization: ADMM solves the nonconvex TRLRF model by alternating updates of TR factors, auxiliary variables, multipliers, and the completed tensor.Observed entries remain fixed while missing entries are approximated from updated TR factors.
- Convergence: TRLRF empirically converges under varied TR-rank and λ choices, although global-minimum convergence is not theoretically guaranteed.Figure 1 averages objective-value curves over 100 independent experiments; stopping uses iteration and relative-change tolerances.
- Computational complexity: Factor-based SVDs reduce the computational scale, with overall complexity O(NR^2I^N + NR^6) when all mode sizes equal I.The SVD component is O(PNR^2), while factor calculations and updates contribute O(NR^3∏N_i I_i + NR^6) and O(NR^6), respectively.
- Computational complexity: The proposed complexity is comparable to HaLRTC and TRALS, while rank-selection robustness can reduce practical model-selection workload and computational cost.The authors report efficient operation on high-order tensors using small TR-ranks.
Experimental Results
Experiments on synthetic tensors, benchmark images, and hyperspectral data show that TRLRF remains robust across TR-rank choices while achieving strong completion performance. Compared with competing methods, its stability is especially evident under excessive rank and higher-order tensor settings.
- Synthetic data: TRLRF achieved the best synthetic-data performance and remained stable as the selected TR-rank increased, whereas TRALS and TRWOPT deteriorated drastically.The comparison used two tensors with missing rate 0.5 and averaged RSE over 100 independent experiments.
- Benchmark images inpainting: On the Lena image with missing rate 0.8, TRLRF outperformed TRALS and TRWOPT for every tested TR-rank.The tested ranks were 4, 6, 8, 10, and 12; TRLRF achieved its highest performance at rank 12.
- Benchmark images inpainting: As TR-rank increased on Lena, TRALS and TRLRF degraded because of redundant model complexity and overfitting, while TRLRF remained effective beyond the desired rank.The passage attributes the robustness to low-rank regularization of the TR factors.
- Benchmark images inpainting: Across eight benchmark images and missing rates from 0.3 to 0.95, TRLRF was compared with seven state-of-the-art completion algorithms using RSE and PSNR.TR-based methods used cross-validation to select ranks, while TRLRF was described as fairly stable across a wide rank range.
- Hyperspectral image: For hyperspectral data at missing rate 0.9, TRLRF provided the best recovery across tested 3-order, 5-order, and 8-order tensor cases.When rank increased from 18 to 22 in 5-order cases, TRLRF stayed steady while TRALS, TRWOPT, and TMac declined; similar behavior appeared for 8-order tensors.
Conclusion
The paper proposes an efficient TR-based tensor completion algorithm that constrains the TR latent space and uses ADMM to address model selection. Experiments show strong performance and lower computational cost than state-of-the-art methods.
- The proposed algorithm imposes low-rank constraints on the TR latent space for tensor completion.
- ADMM efficiently solves the model while addressing model selection in traditional tensor completion methods.
- Experiments on synthetic and real-world data show that the algorithm outperforms state-of-the-art methods.
- The method is general enough to extend to other tensor decompositions for developing more efficient and robust algorithms.