Research map / Learning theory and algorithms / Matrix and tensor methods
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves exponential query lower bounds for trace, spectral norm, and zero-testing under Kronecker matrix-vector queries (adaptive, under a conditioning assumption), and shows Rademacher-product queries need Theta(2^q) queries for zero testing versus one Gaussian query.
Problem
Query complexity of estimating trace, top eigenvalue/spectral norm, and testing whether a matrix is zero when the matrix is accessed only through Kronecker-structured matrix-vector products.
Approach
Random Kronecker-structured vectors have exponentially smaller inner products with fixed Kronecker-structured vectors than unstructured random vectors, so a planted random Kronecker vector is hidden from Kronecker queries; combined with an information-theoretic adaptive-query argument and small-alphabet orthogonality, this yields exponential lower bounds and a Rademacher-vs-Gaussian gap.
Key results
- Any kappa-conditioned Kronecker matrix-vector algorithm estimating the top eigenvalue to within (1±1/2) needs t >= C^q queries (informal theorem).
- Zero testing with Rademacher Kronecker queries requires Theta(2^q) queries for n=2, whereas a single Gaussian Kronecker query decides zero-ness with probability 1.
- Zero testing over the complex alphabet {±1, ±i} requires Omega((4/3)^q) queries for n=2, showing the real {±1} alphabet is harder than the complex one.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Kronecker Rademacher vectors instead of a Kronecker product of Gaussian vectors | Zero testing · Real Kronecker zero testing | queries: a single query -> Θ(2^q) | Hurt |
| Use the complex alphabet {−1, 1, i, −i} instead of the real alphabet {−1, 1} | Kronecker zero testing, n=2 · Zero testing | queries: Θ(2^q) -> Θ ((4/3)^q) | Helped |
| Use Rademacher Kronecker queries rather than continuous random variables | Trace estimation of PSD matrices, n=2 · PSD trace estimation | queries: O(1.5^q) -> Θ(2^q) | Hurt |
| Use Kronecker-structured queries for spectral norm estimation | κ-conditioned algorithms on symmetric matrices · Spectral norm estimation | queries: Ω(min{C_0^{q/2}, C_τ^{q/2}/κ^2}) | Hurt |
| Use κ-conditioned Kronecker vector-matrix-vector queries for trace estimation | PSD trace estimation · Trace estimation | queries: Ω(min{C_0^{q/2}, C_τ^{q/2}/(κ^2 √ε)}) | Hurt |
Surprising findings
- Subgaussian sketches with the same norm can differ exponentially in query complexity under the Kronecker model (Rademacher vs Gaussian).
- Kronecker Rademacher trace estimation is exponentially worse than Kronecker random unit vectors (O(1.5^q) for PSD trace with n=2).
Limitations
- Lower bounds require a condition-number assumption on the algorithm's query matrix (kappa-conditioned).
- Complex-vs-real gap is not apples-to-apples since alphabet sizes differ.
- Upper bounds for general Kronecker algorithms and tight trace estimation bounds remain open.
Experimental setup
Metrics: query complexity
Baselines: Kronecker JL Kronecker Hutchinson Hutchinson estimator
Builds on: Simchowitz et al. matrix-vector lower bounds Hutchinson trace estimator Khatri-Rao sketching
Closest papers by meaning
- The Structural Complexity of Matrix-Vector Multiplication (NeurIPS 2025 · similarity 0.87)
- How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation (ICLR 2024 · similarity 0.84)
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.82)
- Simple Randomized Rounding for Max-Min Eigenvalue Augmentation (ICML 2025 · similarity 0.82)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.82)
- A Near Linear Query Lower Bound for Submodular Maximization (ICML 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.