Adaptive Randomized Pivoting for Tensor Singular Value Decomposition Model

This paper studies how adaptive randomized pivoting (ARP), recently introduced for matrix column subset selection, can be extended to tensors in the t-product framework.

We propose two constructions.

The first one, called ARP-T-CUR, applies matrix ARP independently to the frontal slices of the tensor in the Fourier domain.

This gives a Fourier-slicewise CUR approximation and leads to a direct expected-error bound inherited from the matrix theory.

The second construction, called T-ARP, selects common lateral and horizontal slices for the whole tensor.

This produces a genuine tensor cross approximation in the t-product sense, but also introduces a new difficulty: the same pivot indices must be used across all Fourier slices.

We make this coupling explicit and prove an expected-error bound under a frequency-alignment condition measuring how far the common tensor-level sampling rule is from the slice-wise ARP sampling rules.

This condition recovers the usual $r+1$-type factor when the leverage-score distributions are aligned across frequencies.

We also discuss the resulting tensor cross approximation and its connection with t-DEIM.

Numerical experiments on synthetic tensors, images, and videos illustrate the behavior of the proposed methods and show the benefit of common-index tensor sampling over standard tensor cross baselines.