More Like this

1. Geometric rank of tensors and subrank of matrix multiplication

   Kopparty, S; Moshkovitz, G; Zuiddam, J. (March 2020, Electronic colloquium on computational complexity)

   Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce the geometric rank as a new tool in the study of tensors and hypergraphs. We prove that the geometric rank is an upper bound on the subrank of tensors and the independence number of hypergraphs. We prove that the geometric rank is smaller than the slice rank of Tao, and relate geometric rank to the analytic rank of Gowers and Wolf in an asymptotic fashion. As a first application, we use geometric rank to prove a tight upper bound on the (border) subrank of the matrix multiplication tensors, matching Strassen's well-known lower bound from 1987. 

   more » « less
2. Concise tensors of minimal border rank

   https://doi.org/10.1007/s00208-023-02569-y  

   Jelisiejew, Joachim; Landsberg, J. M.; Pal, Arpan (April 2023, Mathematische Annalen)

   We determine defining equations for the set of concise tensors of minimal border rank in Cm⊗Cm⊗Cm when m = 5 and the set of concise minimal border rank 1∗-generic tensors when m = 5, 6. We solve the classical problem in algebraic complexity theory of classifying minimal border rank tensors in the special case m = 5. Our proofs utilize two recent developments: the 111-equations defined by Buczy´nska–Buczy´nski and results of Jelisiejew–Šivic on the variety of commuting matrices. We introduce a new algebraic invariant of a concise tensor, its 111-algebra, and exploit it to give a strengthening of Friedland’s normal form for 1-degenerate tensors satisfying Strassen’s equations. We use the 111-algebra to characterize wild minimal border rank tensors and classify them in C5⊗C5⊗C5. 

   more » « less
3. ISLET: Fast and Optimal Low-Rank Tensor Regression via Importance Sketching

   https://doi.org/10.1137  

   Zhang, A. R; Luo, Y; Raskutti, G; Yuan, M. (June 2020, SIAM journal on mathematics of data science)

   In this paper, we develop a novel procedure for low-rank tensor regression, namely Importance Sketching Low-rank Estimation for Tensors (ISLET). The central idea behind ISLET is importance sketching, i.e., carefully designed sketches based on both the responses and low-dimensional structure of the parameter of interest. We show that the proposed method is sharply minimax optimal in terms of the mean-squared error under low-rank Tucker assumptions and under the randomized Gaussian ensemble design. In addition, if a tensor is low-rank with group sparsity, our procedure also achieves minimax optimality. Further, we show through numerical study that ISLET achieves comparable or better mean-squared error performance to existing state-of-the-art methods while having substantial storage and run-time advantages including capabilities for parallel and distributed computing. In particular, our procedure performs reliable estimation with tensors of dimension $p = O(10^8)$ and is 1 or 2 orders of magnitude faster than baseline methods. 

   more » « less
4. Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruptions

   https://doi.org/10.1137/23M1574282  

   Cai, HanQin; Chao, Zehan; Huang, Longxiu; Needell, Deanna (March 2024, SIAM Journal on Imaging Sciences)

   We study the tensor robust principal component analysis (TRPCA) problem, a tensorial extension of matrix robust principal component analysis, which aims to split the given tensor into an underlying low-rank component and a sparse outlier component. This work proposes a fast algorithm, called robust tensor CUR decompositions (RTCUR), for large-scale nonconvex TRPCA problems under the Tucker rank setting. RTCUR is developed within a framework of alternating projections that projects between the set of low-rank tensors and the set of sparse tensors. We utilize the recently developed tensor CUR decomposition to substantially reduce the computational complexity in each projection. In addition, we develop four variants of RTCUR for different application settings. We demonstrate the effectiveness and computational advantages of RTCUR against state-of-the-art methods on both synthetic and real-world datasets. 

   more » « less
5. A note on tight projective 2‐designs

   https://doi.org/10.1002/jcd.21804  

   Iverson, Joseph W.; King, Emily J.; Mixon, Dustin G. (September 2021, Journal of Combinatorial Designs)

   Abstract We study tight projective 2‐designs in three different settings. In the complex setting, Zauner's conjecture predicts the existence of a tight projective 2‐design in every dimension. Pandey, Paulsen, Prakash, and Rahaman recently proposed an approach to make quantitative progress on this conjecture in terms of the entanglement breaking rank of a certain quantum channel. We show that this quantity is equal to the size of the smallest weighted projective 2‐design. Next, in the finite field setting, we introduce a notion of projective 2‐designs, we characterize when such projective 2‐designs are tight, and we provide a construction of such objects. Finally, in the quaternionic setting, we show that every tight projective 2‐design for determines an equi‐isoclinic tight fusion frame of subspaces of of dimension 3. 

   more » « less