Adaptive Randomized Pivoting for Tensor Cross Approximation in the T-Product Framework
Abstract
This paper studies extensions of adaptive randomized pivoting (ARP), recently introduced for matrix column subset selection, to tensors in the t-product framework. We propose two constructions. ARP-T-CUR applies matrix ARP-cross at the nonredundant Fourier frequencies and uses conjugate symmetry to preserve real-valued tensors. Assuming that the selected intersections are nonsingular almost surely, the matrix theory gives a direct expected-error bound for this Fourier-slicewise approximation. T-ARP instead selects common lateral and horizontal slices, with the same indices used at every Fourier frequency. This common-index constraint requires a new analysis. Under frequency-alignment and frequency-wise rank-growth assumptions, we prove an expected-error bound and recover the matrix ARP factor r+1 when the frequency-wise sampling distributions are aligned. We also derive bounds for tensor cross approximation and t-DEIM. The numerical experiments show that both proposed methods give accurate tensor approximations and perform favorably against the considered slice-selection baselines. A separate full-enumeration experiment verifies the assumptions and the expected-error bound for common-index T-ARP.
Related
- Sharp bounds for non-adaptive randomized approximation of high-dimensional vectors
- Large Growth Happens: Gaussian Elimination with Partial Pivoting on Random Matrices
- Efficient Low-Rank Approximation of Quaternion Matrices via Adaptive Cross Approximation
- Adaptive multigrid for high-order discontinuous Galerkin methods based on the full approximation scheme
- hp-adaptive trees for graph signal approximation
BibTeX
@misc{akdodshoev2026adaptive,
title = {{Adaptive Randomized Pivoting for Tensor Cross Approximation in the T-Product Framework}},
author = {Ahmadsho Akdodshoev and Valentin Leplat and Salman Ahmadi-Asl},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2606.26688},
eprint = {2606.26688},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.26688},
}
RIS
TY - UNPB
TI - Adaptive Randomized Pivoting for Tensor Cross Approximation in the T-Product Framework
AU - Ahmadsho Akdodshoev
AU - Valentin Leplat
AU - Salman Ahmadi-Asl
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2606.26688
UR - https://arxiv.org/abs/2606.26688
AB - This paper studies extensions of adaptive randomized pivoting (ARP), recently introduced for matrix column subset selection, to tensors in the t-product framework. We propose two constructions. ARP-T-CUR applies matrix ARP-cross at the nonredundant Fourier frequencies and uses conjugate symmetry to preserve real-valued tensors. Assuming that the selected intersections are nonsingular almost surely, the matrix theory gives a direct expected-error bound for this Fourier-slicewise approximation. T-ARP instead selects common lateral and horizontal slices, with the same indices used at every Fourier frequency. This common-index constraint requires a new analysis. Under frequency-alignment and frequency-wise rank-growth assumptions, we prove an expected-error bound and recover the matrix ARP factor r+1 when the frequency-wise sampling distributions are aligned. We also derive bounds for tensor cross approximation and t-DEIM. The numerical experiments show that both proposed methods give accurate tensor approximations and perform favorably against the considered slice-selection baselines. A separate full-enumeration experiment verifies the assumptions and the expected-error bound for common-index T-ARP.
ER -