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. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits

   https://doi.org/10.1145/3406325.3451096  

   Bhargava, Vishwas; Saraf, Shubhangi; Volkovich, Ilya (June 2021, STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((k) circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d, but is interesting even for d=3. 2) Sums of powers of constantly many linear forms ((k) circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear (k) circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of (k) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’). 

   more » « less