More Like this

1. On Multilinear Forms: Bias, Correlation, and Tensor Rank

   Bhrushundi, Abhishek; Harsha, Prahladh; Hatami, Pooya; Kopparty, Swastik; Kumar, Mrinal (August 2020, Leibniz international proceedings in informatics)

   Byrka, Jaroslaw; Meka, Raghu (Ed.)

   In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d. 

   more » « less
2. Fast and low-memory compressive sensing algorithms for low tucker-rank tensor approximation from streamed measurements

   https://doi.org/10.1007/s11075-025-02101-0  

   Haselby, Cullen; Iwen, Mark_A; Needell, Deanna; Rebrova, Elizaveta; Swartworth, William (May 2025, Numerical Algorithms)

   Abstract In this paper we consider the problem of recovering a low-rank Tucker approximation to a massive tensor based solely on structured random compressive measurements (i.e., a sketch). Crucially, the proposed random measurement ensembles are both designed to be compactly represented (i.e., low-memory), and can also be efficiently computed in one-pass over the tensor. Thus, the proposed compressive sensing approach may be used to produce a low-rank factorization of a huge tensor that is too large to store in memory with a total memory footprint on the order of the much smaller desired low-rank factorization. In addition, the compressive sensing recovery algorithm itself (which takes the compressive measurements as input, and then outputs a low-rank factorization) also runs in a time which principally depends only on the size of the sought factorization, making its runtime sub-linear in the size of the large tensor one is approximating. Finally, unlike prior works related to (streaming) algorithms for low-rank tensor approximation from such compressive measurements, we present a unified analysis of both Kronecker and Khatri-Rao structured measurement ensembles culminating in error guarantees comparing the error of our recovery algorithm’s approximation of the input tensor to the best possible low-rank Tucker approximation error achievable for the tensor by any possible algorithm. We further include an empirical study of the proposed approach that verifies our theoretical findings and explores various trade-offs of parameters of interest. 

   more » « less
3. Approximately low-rank recovery from noisy and local measurements by convex program

   https://doi.org/10.1093/imaiai/iaad013  

   Lee, Kiryung; Sharma, Rakshith Srinivasa; Junge, Marius; Romberg, Justin (May 2023, Information and Inference: A Journal of the IMA)

   Abstract Low-rank matrix models have been universally useful for numerous applications, from classical system identification to more modern matrix completion in signal processing and statistics. The nuclear norm has been employed as a convex surrogate of the low-rankness since it induces a low-rank solution to inverse problems. While the nuclear norm for low rankness has an excellent analogy with the $$\ell _1$$ norm for sparsity through the singular value decomposition, other matrix norms also induce low-rankness. Particularly as one interprets a matrix as a linear operator between Banach spaces, various tensor product norms generalize the role of the nuclear norm. We provide a tensor-norm-constrained estimator for the recovery of approximately low-rank matrices from local measurements corrupted with noise. A tensor-norm regularizer is designed to adapt to the local structure. We derive statistical analysis of the estimator over matrix completion and decentralized sketching by applying Maurey’s empirical method to tensor products of Banach spaces. The estimator provides a near-optimal error bound in a minimax sense and admits a polynomial-time algorithm for these applications. 

   more » « less
4. Bayesian Generalized Sparse Symmetric Tensor-on-Vector Regression

   https://doi.org/10.1080/00401706.2020.1784799  

   Guha, Sharmistha; Guhaniyogi, Rajarshi (June 2020, Technometrics)

   Motivated by brain connectome datasets acquired using diffusion weighted magnetic resonance imaging (DWI), this article proposes a novel generalized Bayesian linear modeling framework with a symmetric tensor response and scalar predictors. The symmetric tensor coefficients corresponding to the scalar predictors are embedded with two features: low-rankness and group sparsity within the low-rank structure. Besides offering computational efficiency and parsimony, these two features enable identification of important “tensor nodes” and “tensor cells” significantly associated with the predictors, with characterization of uncertainty. The proposed framework is empirically investigated under various simulation settings and with a real brain connectome dataset. Theoretically, we establish that the posterior predictive density from the proposed model is “close” to the true data generating density, the closeness being measured by the Hellinger distance between these two densities, which scales at a rate very close to the finite dimensional optimal rate, depending on how the number of tensor nodes grow with the sample size. 

   more » « less
5. Motives of melonic graphs

   https://doi.org/10.4171/AIHPD/156  

   Aluffi, Paolo; Marcolli, Matilde; Qaisar, Waleed (July 2023, Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions)

   We investigate recursive relations for the Grothendieck classes of the affine graph hypersurface complements of melonic graphs. We compute these classes explicitly for several families of melonic graphs, focusing on the case of graphs with valence-4internal vertices, relevant to CTKT tensor models. The results hint at a complex and interesting structure in terms of divisibility relations or nontrivial relations between classes of graphs in different families. Using the recursive relations, we prove that the Grothendieck classes of all melonic graphs are positive as polynomials in the class of the moduli space\mathcal M_{0,4}. We also conjecture that the corresponding polynomials arelog-concave, on the basis of hundreds of explicit computations. 

   more » « less