Low rank tensor recovery via iterative hard thresholding

Holger Rauhut; Reinhold Schneider; Zeljka Stojanac

Source-linked AI summary

Low rank tensor recovery via iterative hard thresholding

Holger Rauhut, Reinhold Schneider, Zeljka Stojanac

arXiv:1602.05217v1Feb 16, 2016cs.ITmath.NAmath.PR

TL;DR

Low-rank tensor recovery lacks the mature theoretical and computational framework available for matrices, while direct tensor nuclear-norm approaches can be intractable. The paper develops iterative hard thresholding for HOSVD, TT, and HT formats and analyzes it through tensor restricted isometry. It proves almost-optimal, up-to-logarithmic-factor measurement bounds for subgaussian maps, extends them to randomized Fourier maps, and reports practical recovery experiments.

Problem
Low-rank tensor recovery from few linear measurements has limited prior theory, and tensor nuclear-norm optimization is generally NP-hard.
Method
The paper analyzes tensor iterative hard thresholding for HOSVD, TT, and HT formats using efficient successive-SVD quasi-best approximations and a decomposition-adapted restricted isometry property.
Results
Subgaussian measurement maps satisfy the tensor restricted isometry property with bounds matching tensor degrees of freedom up to logarithmic factors, and analogous bounds hold for randomized Fourier maps.
Takeaways & Limitations
The results provide a tractable tensor-recovery approach with near-optimal measurement scaling across HOSVD, TT, and HT formats, supported by numerical experiments.
Takeaways & Limitations
Convergence is only partial: it requires an iterate-dependent condition whose satisfaction cannot be guaranteed a priori, and the intermediate phase remains unresolved.

Abstract

from arXiv · show

We study extensions of compressive sensing and low rank matrix recovery (matrix completion) to the recovery of low rank tensors of higher order from a small number of linear measurements. While the theoretical understanding of low rank matrix recovery is already well-developed, only few contributions on the low rank tensor recovery problem are available so far. In this paper, we introduce versions of the iterative hard thresholding algorithm for several tensor decompositions, namely the higher order singular value decomposition (HOSVD), the tensor train format (TT), and the general hierarchical Tucker decomposition (HT). We provide a partial convergence result for these algorithms which is based on a variant of the restricted isometry property of the measurement operator adapted to the tensor decomposition at hand that induces a corresponding notion of tensor rank. We show that subgaussian measurement ensembles satisfy the tensor restricted isometry property with high probability under a certain almost optimal bound on the number of measurements which depends on the corresponding tensor format. These bounds are extended to partial Fourier maps combined with random sign flips of the tensor entries. Finally, we illustrate the performance of iterative hard thresholding methods for tensor recovery via numerical experiments where we consider recovery from Gaussian random measurements, tensor completion (recovery of missing entries), and Fourier measurements for third order tensors.

1 Introduction and Motivation

The paper develops tractable iterative hard-thresholding methods for recovering low-rank tensors in HOSVD, TT, and HT formats, addressing the computational difficulty of tensor recovery. It also establishes near-optimal measurement bounds for tensor restricted isometry and extends them to randomized Fourier maps.

Motivation: Tensor nuclear-norm optimization is generally NP-hard, motivating tractable alternatives for low-rank tensor recovery.This difficulty applies to tensors of order d ≥ 3 and to reasonable notions of tensor rank.
Method: The paper introduces tensor iterative hard thresholding for HOSVD, TT, and HT decompositions, using efficient successive-SVD projections onto format-specific low-rank tensors.These projections are quasi-best rather than generally optimal low-rank approximations.
Analysis: The convergence analysis uses a tensor restricted isometry property adapted to the selected tensor decomposition and additionally requires a condition on the iterates.The result is partial because the required approximation condition cannot be guaranteed a priori.
Measurement bounds: Subgaussian measurement maps satisfy the relevant tensor restricted isometry property with bounds that, up to logarithmic factors, match the degrees of freedom of the tensor format.The bounds are stated for HOSVD, TT, and HT rank structures.
Fourier measurements: Random sign flips followed by Fourier transformation and random subsampling provide an analogous measurement result for tensor recovery.The paper also presents numerical experiments involving third-order tensor recovery.

2 Tensor decompositions and tensor rank

The paper introduces HOSVD, HT, and TT tensor formats, each with an associated rank notion and efficient quasi-best low-rank approximation procedures. HOSVD can suffer exponential dependence on tensor order, whereas hierarchical formats avoid this scaling under moderate ranks.

HOSVD: HOSVD represents a tensor using orthogonal mode bases and an all-orthogonal core whose subtensors are ordered by Frobenius norm.Its rank is a tuple determined by the matrix ranks of tensor unfoldings.
HOSVD: For high order d, the HOSVD core can contain r^d entries, causing the number of degrees of freedom to scale exponentially with d.Without additional core sparsity, the Tucker format is therefore most suitable for low-order tensors such as d = 3.
HOSVD: HOSVD rank-r truncation retains the leading singular vectors of every unfolding and the corresponding core subtensor.The resulting approximation is quasi-best rather than generally optimal, because the best tensor approximation is NP-hard to compute.
Hierarchical Tucker: HT organizes tensor subspaces through a partition tree, recursively combining child subspaces into parent subspaces with transfer tensors and frames.A rank tuple assigns ranks to the tree vertices and corresponds to ranks of the associated matricizations.
Hierarchical Tucker: A rank-r HT tensor can be stored using transfer tensors and leaf frames in O(ndr + dr^3) data, without exponential dependence on tensor order.Best rank-r approximation remains NP-hard, but successive SVDs provide an efficiently computable quasi-best approximation.
Tensor Train: TT is the unbalanced-tree special case of hierarchical tensor decomposition, with ranks defined by selected matricizations and quasi-best truncation computed efficiently.Its representation uses a root tensor and component tensors arranged along the tensor-train hierarchy.

3 Analysis of iterative hard thresholding

The paper develops tensor iterative hard thresholding methods for HOSVD, TT, and HT formats and proves partial convergence under a format-specific tensor restricted isometry property. The guarantees include exact recovery for sufficiently low-rank tensors and error bounds with noisy measurements, but rely on an additional condition involving the computed approximation.

Algorithm: Tensor IHT starts from an initial guess and alternates measurement-residual updates with low-rank projections tailored to HOSVD, TT, or HT.The projection operators are constructed from singular-vector spaces of tensor matricizations and the chosen decomposition tree.
Algorithm variants: NTIHT provides better convergence results than CTIHT, but each iteration is substantially slower because it recomputes the tensor decomposition.CTIHT uses step length µj = 1, whereas NTIHT uses normalized projection operators.
TRIP-based analysis: The analysis assumes a tensor restricted isometry property whose definition depends on the tensor format and its induced rank.The paper considers HOSVD-TRIP, TT-TRIP, and HT-TRIP as tensor analogues of the matrix and sparse-vector RIP.
Convergence: Under TRIP and an additional approximation condition, CTIHT and NTIHT converge to an exactly rank-r tensor from noiseless measurements.The condition is not directly checkable and is stronger than the basic TRIP assumption.
Convergence: With noisy measurements, the same condition yields an iteration-dependent recovery error controlled by the measurement noise.The stated bound is proportional to ∥e∥2 through the factor 1 − a.
Limitations: The convergence theorem does not directly cover approximate low-rank tensors with a tensor analogue of the matrix nuclear-norm error estimate.The paper represents the approximation residual as part of the effective noise, but notes that the corresponding tensor approximation error is unclear.

4 Tensor RIP

This section establishes tensor restricted isometry guarantees for HOSVD, TT, and HT formats by bounding covering numbers of their low-rank tensor sets. Random subgaussian measurement ensembles satisfy the resulting TRIP with high probability under format-dependent measurement conditions.

Measurement ensembles: The measurement-count question is studied for subgaussian maps and, subsequently, maps based on partial random Fourier transforms.The bounds depend on tensor rank, order, and mode dimensions.
Measurement ensembles: An L-subgaussian ensemble has independent, mean-zero, variance-one, L-subgaussian entries; Gaussian and Bernoulli ensembles are special cases.The paper also allows a formulation in terms of independent sensing tensors rather than fully independent entries.
TRIP guarantee: Theorem 2 states that random L-subgaussian maps satisfy the TRIP for HOSVD, TT, or HT with probability at least 1 − ε under the stated measurement bound.The bound uses the rank tuple and dimensions associated with the selected tensor format.
Proof strategy: The proof uses ε-nets and covering numbers to control the sets of unit-norm low-rank tensors for each tensor format.For HOSVD, the construction separately covers orthonormal factor matrices and the core tensor.
Proof strategy: For HT and TT formats, the covering-number analysis uses a decomposition tree and a right-orthogonal representation of the tensor factors.The TT decomposition is treated as a special case within the HT framework.

5 Random Fourier measurements

The paper extends randomized Fourier measurements to tensors by combining random sign flips, a multidimensional Fourier transform, and random subsampling. The resulting map satisfies the tensor restricted isometry property with an almost optimal number of measurements, though logarithmic factors may be improvable.

Motivation: Randomized Fourier measurements address the lack of structure and fast multiplication routines in subgaussian measurement maps.The construction is motivated by the practical limitations of unstructured random measurements.
Construction: The tensor measurement map composes independent random sign flips, a d-dimensional Fourier transform, and uniform random subsampling.The Fourier transform may also be applied to the vectorized tensor without changing the stated results.
Guarantee: The randomized Fourier map satisfies the TRIP for an almost optimal number of measurements.The result applies to the tensor formats analyzed in the paper through the corresponding tensor restricted isometry constant.
Guarantee: For HOSVD, the stated bound includes log(d), while the TT and HT bounds include log(dr).Here n = max{n_i : i ∈ [d]} and r = max{r_t : t ∈ T_I}.
Analysis: The Fourier-map theorem is obtained using a deviation bound for randomized Fourier matrices and estimates of the relevant complexity quantities.The proof applies the general Fourier result to the tensor-rank sets used for HOSVD and hierarchical Tucker formats.
Caveat: Improved estimates for standard random partial Fourier matrices may reduce logarithmic factors in the stated bounds.This is presented as a possible improvement rather than an established result.

6 Numerical results

The numerical study evaluates tensor iterative hard thresholding for third-order HOSVD recovery under Gaussian measurements, randomized Fourier measurements, and tensor completion. Experiments vary tensor dimensions and unfolding ranks, and report successful recovery across 200 simulations using CTIHT and NTIHT.

Experimental setup: The experiments test CTIHT and NTIHT on third-order tensors using Gaussian, randomized Fourier, and tensor-completion measurements.Tensor completion denotes recovery from randomly chosen tensor entries.
Experimental setup: The study includes cubic 10 × 10 × 10 tensors with equal and unequal unfolding ranks and non-cubic 6 × 10 × 15 tensors with equal ranks.For fixed dimensions, HOSVD rank, and measurement count, each configuration uses 200 simulations.
Evaluation: The recovery experiments use prescribed residual thresholds and stop after convergence or at 5000 iterations.The convergence threshold is ||X_{j+1} − X_j||_F < 10^-4.
Implementation: Gaussian measurement operators are generated from tensors with independent Gaussian entries and act through Frobenius inner products.The measurements are defined by [A(X)](k) = ⟨X, A_k⟩.
Implementation: The tested tensors are generated from Tucker decompositions with Gaussian core entries and Gaussian-derived singular-vector factors.The factor matrices use leading left singular vectors of independent Gaussian matrices.
Implementation: The Fourier operator and its adjoint are applied efficiently using the FFT, enabling reasonable runtimes for comparatively large tensor dimensions.The implementation uses TensorLab for HOSVD decomposition and truncation.
Evaluation: Recovery plots use the number of measurements relative to the degrees of freedom of an arbitrary tensor, with successful-recovery percentage on the vertical axis.The plotted measurement count is normalized through the degrees of freedom reference.
Evaluation: Table 6 compares CTIHT and NTIHT across Gaussian measurements, Fourier ensembles, and tensor completion.m0 is the smallest measurement count achieving full recovery, while m1 is the largest count at which none of 200 tensors is recovered.