Refining Dual Spectral Sparsity in Transformed Tensor Singular Values

Andong Wang, Yuning Qiu, Haonan Huang, Zhong Jin, Guoxu Zhou, Qibin Zhao

Introduction: The Limitations of the Tubal Nuclear Norm

Tensors—multi-dimensional arrays—are the natural mathematical language for complex, real-world data, ranging from hyperspectral satellite imagery to medical MRI volumes. To reconstruct these tensors from noisy or incomplete observations, researchers typically rely on the Tubal Nuclear Norm (TNN), derived from the tensor Singular Value Decomposition (t-SVD).

While TNN is a widely used low-rank modeling tool that promotes sparsity of frequency-domain singular values, it suffers from a "one-size-fits-all" limitation. As a direct extension of the matrix nuclear norm, TNN applies a uniform, element-wise penalty to transformed singular values. Crucially, it fails to distinguish between two distinct structural properties inherent to real-world hierarchical data:

  1. Inter-frequency sparsity: Most "frequency slices" contain almost no energy.
  2. Intra-frequency low-rankness: The few slices that do contain energy are highly structured and low-rank.

Because standard TNN cannot differentiate between a frequency slice that is "weak but full-rank" and one that is "strong but low-rank," its performance is inherently restricted on complex datasets where spectral energy is concentrated in a tiny subset of the spectrum.

The Proposed Solution: Tensor $\ell_p$-Schatten-$q$ Quasi-Norm

To overcome this limitation, the authors propose a more nuanced and flexible regularizer: the tensor $\ell_p$-Schatten-$q$ quasi-norm ($p, q \in (0, 1]$). This novel mathematical framework explicitly captures and controls the "dual spectral sparsity" of tensor data by decoupling the two levels of structure.

The core innovation lies in the introduction of two tunable parameters:

  • The $p$ parameter controls sparsity across frequencies (inter-frequency). It acts as a filter, selecting only the most informative frequency slices.
  • The $q$ parameter controls the low-rankness within each active slice (intra-frequency), enforcing a low-rank structure only where it matters.

By separating $p$ and $q$, the model can be tuned to the specific physics of the data. This formulation includes TNN as a special case and subsumes several existing tensor regularizers by coupling global frequency sparsity with local spectral low-rankness.

Theoretical and Algorithmic Contributions

Because the proposed quasi-norm is non-convex, it presents a notoriously difficult optimization challenge. To address this, the authors developed a reweighted ADMM-based algorithm that utilizes a weighted $\ell_{1/2}$ proxy to iteratively solve the problem.

Beyond the algorithmic contribution, the paper establishes rigorous minimax error bounds under the proposed dual spectral sparsity model. This theoretical "speed limit" defines the best possible accuracy any algorithm could achieve given the data's structure. The authors demonstrate that the estimation difficulty is fundamentally a sum of two costs: the combinatorial cost of identifying the correct active frequencies, and the parametric cost of estimating the low-rank matrices within them.

Experimental Validation and Key Results

The authors validated their approach across a massive range of data types, including hyperspectral (Salinas A, Indian Pines), multispectral (Columbia MSI), medical/scientific (Brain MRI, CT scans, thermal imagery), video sequences, and image clustering benchmarks (FRDUE, PIE10, USPS1000).

Key findings include:

  • Superior Recovery: In noisy tensor completion tasks, the proposed method consistently outperformed TNN and other baselines (such as SNN and $k$-support norms) by 2–4 dB in PSNR across various sampling ratios.
  • Robustness to Noise: The method proved highly effective not only against standard Gaussian noise but also against Poisson noise, which is critical for photon-limited imaging applications like night vision or medical X-rays.
  • Enhanced Clustering: When applied to image clustering, the dual-sparse prior produced more discriminative representations, leading to higher Accuracy (ACC) and Normalized Mutual Information (NMI) compared to state-of-the-art subspace clustering methods.

Limitations and Future Directions

While the tensor $\ell_p$-Schatten-$q$ quasi-norm achieves state-of-the-art performance, the authors note a few limitations and avenues for future research:

  • Computational Complexity: The current solver requires full Singular Value Decompositions (SVDs) for every frequency slice. While parallelizable, this is computationally expensive for massive tensors. Future iterations may explore truncated or randomized SVDs to improve scalability.
  • Parameter Tuning: Although the results are stable and the authors suggest a "sweet spot" of $p \approx 0.8$ and $q \approx 0.81$, developing a fully automated, data-driven method to select these values (potentially via bilevel optimization) remains an open question.
  • Task-Specific Theory: The current minimax analysis applies to a general "location model." Extending these theoretical bounds to specific inverse problems, such as compressed sensing, would provide even tighter guarantees for practical engineering applications.

Summary updated

Abstract

The Tubal Nuclear Norm (TNN), derived from the tensor Singular Value Decomposition (t-SVD), is a widely used low-rank modeling tool that promotes sparsity of frequency-domain singular values. However, as a direct extension of the matrix nuclear norm, TNN applies a uniform element-wise penalty to transformed singular values, without explicitly distinguishing sparsity across frequency components from low-rankness within each component. This can be restrictive for real-world tensor data that exhibit multi-level spectral structures, where spectral energy is concentrated in a subset of frequency components while active components remain low-rank. To overcome this limitation, we propose the tensor $\ell_p$-Schatten-$q$ quasi-norm ($p,q\in(0,1]$), which enables explicit control of dual spectral sparsity by jointly regularizing inter-frequency sparsity and intra-frequency low-rankness. This formulation includes TNN as a special case and subsumes several existing tensor regularizers by coupling global frequency sparsity with local spectral low-rankness, yielding a more flexible modeling principle. We establish minimax error bounds under the proposed dual spectral sparsity model, develop a reweighted optimization algorithm for the resulting nonconvex problem, and demonstrate its effectiveness and robustness on noisy and Poisson tensor completion as well as image clustering tasks.
BibTeX
@inproceedings{wang2026refining,
  author = {Andong Wang and Yuning Qiu and Haonan Huang and Zhong Jin and Guoxu Zhou and Qibin Zhao},
  title = {{Refining Dual Spectral Sparsity in Transformed Tensor Singular Values}},
  booktitle = {International Conference on Machine Learning},
  year = {2026},
  url = {https://openreview.net/forum?id=1ZIjW3LFcH},
}
Figure