An Optimal Least-Square Solver For Scaled Partial-Isometric Linear Systems

2025/07/02 by Kar, Suvendu, Murugesan Venkatapathi, Venkatapathi, Murugesan
Computer Science · Mathematics · Physics and Astronomy · #Matrix Theory and Algorithms #Advanced Optimization Algorithms Research #Model Reduction and Neural Networks

paper · pdf · doi:10.48550/arxiv.2507.01434

Abstract

We present an O(mn) direct least-squares solver for m × n linear systems with a scaled partial isometry. The proposed algorithm is also useful when the system is block diagonal and each block is a scaled partial isometry with distinct scaling factors. We also include numerical experiments as a demonstration.

Citations

• Partially isometric matrices: a brief and selective survey
• Optimal Tight Frames and Quantum Measurement
• Partial dynamical systems and C*-algebras generated by partial isometries

Related

• Matrix Scaling and Balancing via Box Constrained Newton's Method and\n Interior Point Methods
• Parallel solution of large sparse linear least squares problems
• LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
• Solving Large Rank-Deficient Linear Least-Squares Problems on Shared-Memory CPU Architectures and GPU Architectures
• A Sherman--Morrison--Woodbury approach to solving least squares problems with low-rank updates