Non-Convex Tensor Recovery from Local Measurements

Tongle Wu, Ying Sun, Jicong Fan

Abstract

Tensor Compressed Sensing (TCS) is a powerful framework for recovering high-dimensional data from limited measurements. However, traditional TCS models often assume global sensing operators, which are impractical for streaming data or distributed systems. This paper introduces a Local TCS model that reconstructs tensors from slice-by-slice measurements. We propose Alt-ScalePGD-Min, a preconditioned non-convex algorithm that achieves fast, linear convergence regardless of the data's condition number. Experimental results on video and MRI data demonstrate that our approach significantly outperforms standard matrix-based recovery and unscaled tensor methods in both speed and reconstruction quality.

Introduction

Recovering a multi-dimensional array (tensor) from a small number of linear measurements is a fundamental challenge in signal processing. While global sensing—where measurements are taken across the entire tensor—is well-studied, it faces significant hurdles in real-time applications like high-resolution video streaming or memory-constrained distributed sensor networks. In these scenarios, data arrives or is stored locally (e.g., frame-by-frame).

The authors address this by formalizing the Local TCS problem. By leveraging the low tubal rank structure (via the t-SVD framework), the model captures spatial-shifting patterns inherent in visual data. The goal is to reconstruct the global low-rank structure from these fragmented, local observations.

Proposed Methodology: Alt-ScalePGD-Min

The recovery is formulated as a non-convex optimization problem where the target tensor is factorized into two components, $U$ and $V$. The authors propose two main algorithms:

  1. Alt-PGD-Min: An alternating minimization scheme using Projected Gradient Descent (PGD).
  2. Alt-ScalePGD-Min: An accelerated version that incorporates a preconditioner—an approximate Hessian matrix. This preconditioning step "normalizes" the gradient, ensuring that the convergence rate remains independent of the data's condition number ($\kappa$).

The recovery follows a two-stage process: a truncated spectral initialization to provide a "warm start" near the global optimum, followed by a local search using the alternating algorithms to refine the factors.

Key Results and Convergence

A primary theoretical and practical contribution is the algorithm's robustness to ill-conditioned data. Standard gradient descent methods often slow down significantly when some underlying signals are much stronger than others.

Performance comparison: PSNR across frames (left) and convergence speed vs iteration number (right). Alt-ScalePGD-Min shows superior stability and rapid linear convergence.

As shown in the convergence plots, Alt-ScalePGD-Min achieves $\epsilon$-accuracy in $O(\log 1/\epsilon)$ iterations. Crucially, while the unscaled Alt-PGD-Min is sensitive to the condition number, the scaled version maintains a consistent, rapid convergence rate that is independent of the data's internal scaling.

Experimental Evaluation

The methods were evaluated on synthetic data, standard video benchmarks (Plane, Akiyo, etc.), and 3D MRI brain volumes.

Video Recovery

In the Plane sequence, the tensor-based approach demonstrated a clear advantage over matrix-based methods. Flattening tensors into 2D matrices destroys multi-dimensional correlations, leading to lower reconstruction quality.

Visual comparison on the 'Plane' sequence. Alt-ScalePGD-Min (PSNR = 41.18) significantly outperforms matrix-based LRcCS (33.69) and unscaled Alt-PGD-Min (30.55).

The visual results confirm that Alt-ScalePGD-Min preserves fine details and structural integrity much better than competing methods, achieving a PSNR of 41.18 compared to 33.69 for the matrix-based LRcCS and 30.55 for the unscaled tensor version.

Medical Imaging

On MRI data from the Simulated Brain Database, the proposed method maintained high structural similarity (SSIM) and feature similarity (FSIM) even with a significantly reduced number of measurements, highlighting its potential for accelerating medical imaging protocols.

Conclusion

This work demonstrates that local tensor sensing is not only feasible but highly effective when paired with preconditioned non-convex optimization. By making convergence independent of the condition number, Alt-ScalePGD-Min provides a robust solution for large-scale, high-dimensional data recovery. Future research will explore removing the requirement for "sample splitting" in theoretical proofs and investigating convergence from random initializations.

Summary updated

BibTeX
@inproceedings{wu2025non,
  author = {Tongle Wu and Ying Sun and Jicong Fan},
  title = {{Non-Convex Tensor Recovery from Local Measurements}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i20.35462},
}
Figure