Low-Rank Tensor Completion by Approximating the Tensor Average Rank

Zhanliang Wang, Junyu Dong, Xinguo Liu, Xueying ZengICCV 2021 · DOI

Abstract

Tensor completion is a critical task in high-dimensional data processing, aiming to recover missing values in multi-dimensional arrays. Traditional methods often rely on convex relaxations like the Tensor Nuclear Norm (TNN), which can lead to biased results due to over-penalization of large singular values. This paper proposes a novel framework based on a "tensor average rank" metric and a nonconvex surrogate function. By employing a proximal Block Coordinate Descent (BCD) algorithm with a coarse-to-fine continuation strategy, the proposed method achieves superior recovery accuracy and significantly faster computation times compared to state-of-the-art techniques.

Introduction

Tensors are the natural format for high-dimensional data such as video, medical imaging, and multi-sensor signals. However, real-world data acquisition often results in incomplete datasets. Tensor completion fills these gaps by assuming the underlying data is "low-rank," meaning it possesses significant internal structure and redundancy.

The challenge lies in defining and minimizing "rank" for tensors. Existing approaches typically unfold tensors into matrices (destroying multi-way correlations), use convex relaxations like TNN (introducing bias), or use Tubal Rank (ignoring fine-grained sparsity). This paper addresses these limitations by introducing a more nuanced rank metric and an unbiased nonconvex optimization framework.

Methodology

The authors propose a framework based on the t-product (tensor-tensor product) under invertible linear transforms.

Tensor Average Rank and Nonconvex Surrogate

They define a new rank metric, the Tensor Average Rank, as the average of the ranks of all frontal slices of a tensor after a specific domain transformation (e.g., Discrete Cosine Transform). To make the NP-hard rank minimization problem tractable, they replace the discrete rank function with a nonconvex surrogate: $\phi_\lambda(x) = \min\{1, \frac{1}{2\lambda}x^2\}$. Unlike convex methods, this function approximates the rank near zero but does not penalize large values once they pass a threshold, preserving the core signal components.

Coarse-to-Fine Optimization

To avoid the local minima inherent in nonconvex optimization, the authors implement a coarse-to-fine strategy (Algorithm 4). They start with a large regularization parameter $\lambda$ and progressively shrink it as the algorithm converges. This "sharpening" allows the algorithm to find a much better global minimum than starting with a strict rank penalty.

Convergence of the proposed Algorithm 4 compared to a fixed regularization parameter, showing the effectiveness of the continuation strategy.

Experimental Setup

The method was evaluated against several benchmarks to test its limits across different sampling rates and ranks:

  • Synthetic Data: Randomly generated low-rank tensors ($40^3$ and $50^3$).
  • Standard Color Images: A set of 8 classic images (e.g., Airplane, Baboon, Lena) at $256 \times 256 \times 3$.
  • Berkeley Segmentation Database (CBSD68): 68 diverse color images for robustness testing.
  • Video Sequences: "Akiyo" and "Container" YUV videos.
Standard color test images used for evaluating tensor completion performance across various benchmarks.

Key Results and Insights

  • Superior Recovery: In synthetic tests, the proposed method recovered tensors at much higher ranks and lower sampling rates than TNN-DCT. For example, at a 50% sampling rate, it recovered tensors with a rank four units higher than previous methods.
  • Visual Quality and PSNR: On standard images at a 20% sampling rate, the method achieved a Peak Signal-to-Noise Ratio (PSNR) of 23.01 dB, outperforming TNN-DCT (22.17 dB) and HaLRTC (20.74 dB).
  • Computational Efficiency: The algorithm is remarkably fast. On standard images, it averaged a runtime of 0.91 seconds, making it more than twice as fast as TNN (2.19s) and significantly faster than SPC (39.83s).

Conclusion and Future Work

The proposed "Average Rank" provides a more granular measure of tensor complexity than "Tubal Rank," asking not just if a tube is non-zero, but how much information it contains. While highly effective, future work could explore optimal linear transform selection for non-natural data (like seismic signals) and extending the framework to N-order tensors for even higher-dimensional applications.

Summary updated

BibTeX
@inproceedings{wang2021low,
  author = {Zhanliang Wang and Junyu Dong and Xinguo Liu and Xueying Zeng},
  title = {{Low-Rank Tensor Completion by Approximating the Tensor Average Rank}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2021},
  doi = {10.1109/iccv48922.2021.00457},
}
Figure