Scholarlink

<p>While leverage score sampling provides powerful tools for approximating solutions to large least squares problems, the cost of computing exact scores and sampling often prohibits practical application. This paper addresses this challenge by developing a new and efficient algorithm for exact leverage score sampling applicable to matrices that are lower column subsets of Kronecker product matrices. We synthesize relevant approximation guarantees and detail the algorithm that specifically leverages this structural property for computational efficiency. Through numerical examples, we demonstrate that utilizing efficiently computed exact leverage scores via our methods significantly reduces approximation errors, as compared to established approximate leverage score sampling strategies when applied to this important class of structured matrices.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Fast algorithms for least squares problems with Kronecker lower subsets

  • 期刊论文

  • 发表日期：

    2026年3月9日

查看全文
  • Osman Asif Malik,
  • Yiming Xu,
  • Nuojin Cheng,
  • Stephen Becker,
  • Alireza Doostan,
  • Akil Narayan

摘要

While leverage score sampling provides powerful tools for approximating solutions to large least squares problems, the cost of computing exact scores and sampling often prohibits practical application. This paper addresses this challenge by developing a new and efficient algorithm for exact leverage score sampling applicable to matrices that are lower column subsets of Kronecker product matrices. We synthesize relevant approximation guarantees and detail the algorithm that specifically leverages this structural property for computational efficiency. Through numerical examples, we demonstrate that utilizing efficiently computed exact leverage scores via our methods significantly reduces approximation errors, as compared to established approximate leverage score sampling strategies when applied to this important class of structured matrices.