{
  "abstract": "We establish matching polynomial query bounds for low-rank approximation from exact matrix--vector products. Given an unknown matrix $A\\in\\mathbb{R}^{m\\times n}$, at each step a randomized algorithm chooses either $v\\in\\mathbb{R}^n$ and receives $Av$, or $u\\in\\mathbb{R}^m$ and receives $A^\\top u$. The choice may depend measurably on all previous queries and replies and on the algorithm's private randomness; each vector product costs one query. The output is a rank-$k$ right projector with Schatten-$p$ residual at most $1+\\varepsilon$ times optimal. Write $N=\\min\\{m,n\\}$ and let $Q_p^*$ denote the worst-case query budget for success probability $2/3$ on every input. For every $1\\le k<N$ and sufficiently small $\\varepsilon$, our lower bounds, combined with existing Krylov upper bounds, give $Q_p^*=\\widetildeΘ\\!\\left(\\min\\{N,k\\min\\{p^{1/6}\\varepsilon^{-1/3},\\varepsilon^{-1/2}\\}\\}\\right)$ $(2\\le p<\\infty)$, $Q_\\infty^*=\\widetildeΘ\\!\\left(\\min\\{N,k\\varepsilon^{-1/2}\\}\\right)$. These bounds have universal constants and allow $p$ to vary with the problem parameters, identifying the transition at $p\\varepsilon\\asymp1$. A complementary result for each fixed $1\\le p<2$ gives $\\widetildeΘ_p(\\min\\{N,k\\varepsilon^{-1/3}\\})$, with constants and an accuracy threshold that may depend on $p$. Together, the results recover this fixed-norm rate for every fixed finite $p$, supplying the multiplicative rank dependence missing from previous lower bounds. Tildes suppress logarithmic factors. The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace. Posterior overlap gives a short fixed-norm argument, while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint. Exact range recovery handles target costs of order $k$; the Wishart family covers the remaining regimes.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.35840",
  "author_total": 8,
  "authors": [
    {
      "name": "Haihan Zhang"
    },
    {
      "name": "Wendao Wu"
    },
    {
      "name": "Chenheng Zhang"
    },
    {
      "name": "Yanyi Li"
    },
    {
      "name": "Chunyuan Zheng"
    },
    {
      "name": "Cong Fang"
    },
    {
      "name": "Haoxuan Li"
    },
    {
      "name": "Zhouchen Lin"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/dv4yy8bc7e2zq.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.35840",
  "fulltext_url": null,
  "id": "dv4yy8bc7e2zq",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.35840",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "openalex",
      "1703|Complexity and Algorithms in Graphs"
    ]
  ],
  "openalex": "W7214981227",
  "pdf_url": "https://arxiv.org/pdf/2609.35840",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-19",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/dv4yy8bc7e2zq.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:31:00Z",
      "native_id": "2609.35840",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.35840"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    }
  ],
  "title": "Matrix-Vector Complexity of Low-Rank Approximation",
  "title_text": "Matrix-Vector Complexity of Low-Rank Approximation",
  "type": "preprint",
  "updated_at": "2026-10-30T12:33:47Z",
  "url": "https://research.draconitic.com/paper/dv4yy8bc7e2zq",
  "venue": "arXiv",
  "versions": []
}