Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms

• URL: http://arxiv.org/abs/2509.21847v1
• Date: Fri, 26 Sep 2025 04:15:29 GMT
• Title: Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms
• Authors: Rohan Deb, Qiaobo Li, Mayank Shrivastava, Arindam Banerjee,
• Abstract summary: We develop a framework to analyze sketched bilinear forms and derive uniform bounds in terms of geometric complexities of the associated sets.<n>This unified analysis recovers known results such as the J-L lemma as special cases, while extending RIP-type guarantees.
• Score: 9.956186859874851
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Uniform bounds on sketched inner products of vectors or matrices underpin several important computational and statistical results in machine learning and randomized algorithms, including the Johnson-Lindenstrauss (J-L) lemma, the Restricted Isometry Property (RIP), randomized sketching, and approximate linear algebra. However, many modern analyses involve *sketched bilinear forms*, for which existing uniform bounds either do not apply or are not sharp on general sets. In this work, we develop a general framework to analyze such sketched bilinear forms and derive uniform bounds in terms of geometric complexities of the associated sets. Our approach relies on generic chaining and introduces new techniques for handling suprema over pairs of sets. We further extend these results to the setting where the bilinear form involves a sum of $T$ independent sketching matrices and show that the deviation scales as $\sqrt{T}$. This unified analysis recovers known results such as the J-L lemma as special cases, while extending RIP-type guarantees. Additionally, we obtain improved convergence bounds for sketched Federated Learning algorithms where such cross terms arise naturally due to sketched gradient compression, and design sketched variants of bandit algorithms with sharper regret bounds that depend on the geometric complexity of the action and parameter sets, rather than the ambient dimension.

Related papers

• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras [0.0]
  We study the underlying algebraic properties of three QAOA ans"atze for the maximum-cut (maxcut) problem on connected graphs.<n>We analyze the standard QAOAsatz as well as the orbit and the multi-angle ansatz.
  arXiv  Detail & Related papers  (2024-10-07T16:46:20Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  We prove upper bounds on the covering number of numerous sets in Euclidean space.<n>We illustrate the power of the result on three computational applications.
  arXiv  Detail & Related papers  (2023-11-09T03:06:59Z)
• SIGMA: Scale-Invariant Global Sparse Shape Matching [50.385414715675076]
  We propose a novel mixed-integer programming (MIP) formulation for generating precise sparse correspondences for non-rigid shapes. We show state-of-the-art results for sparse non-rigid matching on several challenging 3D datasets.
  arXiv  Detail & Related papers  (2023-08-16T14:25:30Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Sharp Analysis of Sketch-and-Project Methods via a Connection to Randomized Singular Value Decomposition [14.453949553412821]
  We develop a theoretical framework for obtaining sharp guarantees on the convergence rate of sketch-and-project methods. We show that the convergence rate improves at least linearly with the sketch size, and even faster when the data matrix exhibits certain spectral decays. Our experiments support the theory and demonstrate that even extremely sparse sketches exhibit the convergence properties predicted by our framework.
  arXiv  Detail & Related papers  (2022-08-20T03:11:13Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Parallelized Computation and Backpropagation Under Angle-Parametrized Orthogonal Matrices [0.0]
  We show how an apparently sequential elementary rotation parametrization can be restructured into blocks of commutative operations. We discuss parametric restrictions of interest to generative modeling and present promising performance results with a prototype GPU implementation.
  arXiv  Detail & Related papers  (2021-05-30T00:47:03Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• A graphical calculus for integration over random diagonal unitary matrices [1.5229257192293197]
  We provide a graphical calculus for computing averages of tensor network diagrams. We exploit the order structure of the partially ordered set of uniform block permutations. A similar calculus is developed for random vectors consisting of independent uniform signs.
  arXiv  Detail & Related papers  (2020-07-22T06:06:51Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.