Source-linked AI summary
Parallel matrix factorization for low-rank tensor completion
Yangyang Xu, Ruru Hao, Wotao Yin, Zhixun Su
TL;DR
The paper addresses recovery of partially observed low-rank higher-order tensors, where exploiting all mode unfoldings and unknown ranks is important. It uses alternating low-rank matrix factorizations with adaptive rank adjustment, and experiments report stronger recovery than compared methods across synthetic and real-world data. The algorithm is non-convex but is observed to perform consistently, with convergence established through vanishing Lagrangian gradients.
Problem
Low-rank tensor completion seeks to recover approximately low-rank tensors from missing entries while addressing the need to exploit all modes and unknown ranks.
Method
The method factorizes every mode unfolding, connects the factorizations through a common variable, cyclically updates variables, and adaptively adjusts rank estimates.
Results
The algorithm consistently outperformed compared tensor-completion methods on synthetic and real-world tests, including solution quality and, against nuclear-norm minimization, running time.
Takeaways & Limitations
All-mode factorization with adaptive rank adjustment recovered a wide variety of low-rank tensors without assuming the true ranks.
Takeaways & Limitations
The approach is non-convex, requires factor sizes to be specified, and its performance can vary with algorithm choices and starting points.
Abstract
from arXiv · showhide
Higher-order low-rank tensors naturally arise in many applications including hyperspectral data recovery, video inpainting, seismic data recon- struction, and so on. We propose a new model to recover a low-rank tensor by simultaneously performing low-rank matrix factorizations to the all-mode ma- tricizations of the underlying tensor. An alternating minimization algorithm is applied to solve the model, along with two adaptive rank-adjusting strategies when the exact rank is not known. Phase transition plots reveal that our algorithm can recover a variety of synthetic low-rank tensors from significantly fewer samples than the compared methods, which include a matrix completion method applied to tensor recovery and two state-of-the-art tensor completion methods. Further tests on real- world data show similar advantages. Although our model is non-convex, our algorithm performs consistently throughout the tests and give better results than the compared methods, some of which are based on convex models. In addition, the global convergence of our algorithm can be established in the sense that the gradient of Lagrangian function converges to zero.
1. Introduction.
The paper frames low-rank tensor completion as recovery of partially observed higher-order tensors while exploiting low-rankness across all mode unfoldings. It proposes alternating matrix-factor updates with adaptive rank adjustment to avoid relying on known ranks.
- Using only one tensor unfolding exploits only one mode’s low-rankness, whereas all-mode low-rankness can provide better performance.
- The model applies low-rank matrix factorizations to every mode unfolding and introduces a common variable constrained to match observed entries.
- Two rank-adjustment schemes decrease overestimated ranks or increase underestimated ranks when the true tensor ranks are unknown.
- Cyclic updates of the factor variables and common variable solve the non-convex model, although a global solution is not guaranteed; limit points satisfy KKT conditions.
2. Phase transition plots.
Phase-transition experiments compare TMac with matrix-completion and tensor-completion baselines on synthetic low-rank tensors. Across the tested datasets, TMac generally recovers more tensors, especially when using more matricization modes or adaptive rank strategies.
- The experiments varied tensor order, rank, and sample ratio across independently repeated synthetic trials.The datasets included 3-way tensors with ranks 5 to 35 and 4-way tensors with ranks 4 to 13; each setting used 50 trials.
- TMac recovered more tensors on the 4-way dataset as it used 1, 2, 3, and 4 matricization modes.The experiment directly compared TMac configurations differing in the number of modes used.
- TMac with rank-fixing and rank-increasing strategies performed significantly better than the compared methods on uniformly random synthetic datasets.The tests used both 3-way and 4-way tensors with uniformly random factor entries.
- On more difficult synthetic datasets with power-law decaying singular values, rank-fixing and rank-increasing TMac strategies performed significantly better than the compared methods.The rank-decreasing strategy could not reduce its estimates to the true rank and performed badly on these datasets.
- TMac was solved using alternating least squares together with two strategies for dynamically adjusting rank estimates.The algorithm was evaluated with rank estimates adjusted because the model requires rank information.
3. Algorithm.
TMac solves low-rank tensor completion by alternating updates of matrix factors across all mode unfoldings, with adaptive rank adjustment when ranks are unknown. The algorithm offers separate rank-decreasing and rank-increasing schemes suited to different tensor structures and objectives.
- Alternating minimization: TMac cyclically updates factor variables for a model that jointly represents all mode unfoldings through a common tensor variable.Each unfolding is approximated by X_nY_n, and cyclic updates exploit blockwise convexity.
- Alternating minimization: The factor updates decompose into N independent least-squares problems that can be solved in parallel.The matrix-factorization formulation avoids repeatedly using SVD-based updates.
- Rank adjustment: Fixed rank estimates can underfit or overfit recovery, so TMac dynamically adjusts each mode rank when the true rank is unknown.Too-small ranks cause large recovery error, while too-large ranks can cause overfitting and deviation from the underlying tensor.
- Rank-decreasing scheme: The rank-decreasing scheme starts from overestimated ranks and reduces them when a large spectral gap identifies a smaller effective rank.The factors are truncated using the leading singular values of the factor product.
- Rank-adjusting strategies: Rank adjustment depends on tensor structure: rank decreasing works well for exactly low-rank tensors, whereas rank increasing is better for approximately low-rank tensors and often favors solution quality.After ranks match the true ranks in the reported experiment, TMac converges linearly.
- Rank-increasing scheme: The rank-increasing scheme starts from underestimated ranks and enlarges them when progress is slow in the current rank-dimensional space.The rank grows by Δr_n up to a specified maximum, using randomly generated directions to augment the factor basis.
4. Convergence analysis.
The convergence analysis establishes that TMac’s cyclic alternating updates have stationary limit points under fixed ranks and positive weights. Specifically, any limit point satisfies the model’s KKT conditions, despite the algorithm being non-convex.
- Algorithm: TMac alternates updates of X, Y, and Z, with initialization satisfying the observed-entry constraint and rank-adjustment branches integrated into the algorithm.The algorithm outputs the updated factor and tensor variables when its stopping criterion is met.
- KKT framework: Introducing a Lagrange multiplier W converts the observation constraint into a Lagrangian whose KKT conditions characterize stationary solutions.The analysis tracks T=(X,Y,Z,W) and its gradient conditions.
- Main convergence result: Under fixed ranks and positive α_n values, any limit point of the generated sequence satisfies the KKT conditions.This is the paper’s main convergence theorem for the alternating minimization algorithm.
- Proof strategy: The proof uses matrix-factorization lemmas involving pseudoinverses, row and column spaces, boundedness, and lower-bounded objective values.These ingredients establish the KKT relations at a convergent subsequence’s limit point.
- Scope: The convergence result does not guarantee a global solution because the underlying optimization problem and algorithm are non-convex.The authors nevertheless report reliable recovery numerically.
5. Numerical experiments.
Experiments compare TMac with MatComp and FaLRTC on MRI, hyperspectral, and video data under missing entries and noise. TMac generally provides better recovery quality than FaLRTC, while performance depends on sampling, mode-wise low-rankness, and weight adaptation.
- Experimental settings: The noisy MRI evaluation retained equality constraints without using prior noise-level information, although the authors note that relaxing them could be better for noisy cases.This is an experimental setting choice rather than a demonstrated limitation of TMac’s recovery model.
- MRI data: TMac consistently achieved lower relative errors than FaLRTC and used less time on the tested brain MRI data.MatComp was fastest and competitive at high sampling rates but performed extremely poorly at low sampling rates such as 10%.
- Hyperspectral data: On hyperspectral data, TMac again outperformed FaLRTC in solution quality and running time, while MatComp had the largest relative errors despite being fastest.Dynamic α_n updates helped at higher sampling rates but could hurt at low sampling rates when entire mode-3 fibers were missing.
- Hyperspectral data: Mode-wise low-rankness explains why dynamic weights help at higher sampling rates but can worsen recovery when a heavily weighted unfolding contains entirely missing columns.Matrix completion cannot recover an entirely missing row or column, limiting the benefit of emphasizing that mode.
- Video inpainting: The video experiments reported comparisons similar to hyperspectral recovery for both grayscale and color data.Results used averages over five independent runs and tested fixed and dynamically updated TMac weights.
6. Discussions.
The proposed method uses all-mode low-rank matrix factorizations and performs strongly on both synthetic and real-world tensor completion tasks. Its algorithm converges quickly in experiments, while future work targets acceleration and richer objectives for higher-order tensors.
- Synthetic tests show recovery of significantly more low-rank tensors than two nuclear-norm models and a one-mode factorization method.
- 3D image and video experiments consistently produce the best solutions among compared methods in solution quality and running time.
- The algorithm converges fast numerically, including linear convergence in Figure 8.
- The authors plan to develop acceleration techniques and incorporate the objective term in (7) for tensors with more than three orders.
7. Figures and tables.
The paper presents figures and tables covering synthetic phase transitions, convergence behavior, and real-data recovery across medical imaging, hyperspectral imaging, and video tasks. These results use multiple tensor orders, factor distributions, noise levels, and sampling ratios.
- The color-video footnote states that the test used the first 150 of 500 frames and that fourth-order recovery was slower without quality improvement.
- Figures 1–7 compare tensor completion methods across 3-way and 4-way synthetic tensors with Gaussian, uniform, or power-law factor structure.
- Figure 3 evaluates TMac using one through four mode matricizations, with mode weights and fixed ranks specified for each configuration.
- Figure 8 examines convergence behavior for two rank-adjusting strategies on Gaussian 50 × 50 × 50 tensors with equal mode rank r.
- Figures 9–12 show original, corrupted, and recovered slices or frames for brain MRI, hyperspectral images, grayscale video, and color video.
- Tables 1–4 report averages over five independent runs under different noise levels and sample ratios for the same four real-world data types.