Factorization-free Orthogonal Projection onto the Positive Semidefinite Cone with Composite Polynomial Filtering

2025/07/12 by Shucheng Kang, Kang, Shucheng, Haoyu Han +5
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Advanced Optimization Algorithms Research #FOS: Mathematics #Matrix Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2507.09165

openalex publication_date 2025/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a factorization-free method for orthogonal projection onto the positive semidefinite (PSD) cone, leveraging composite polynomial filtering. Inspired by recent advances in homomorphic encryption, our approach approximates the PSD cone projection operator using a carefully optimized composite polynomial evaluated exclusively via matrix-matrix multiplications. This approach enables efficient GPU implementations with low-precision arithmetic, significantly outperforming the classical PSD cone projection using state-of-the-art GPU-based eigenvalue decomposition solvers. Specifically, our method achieves a consistent relative error of 10^-3 in half-precision arithmetic with only 22 matrix-matrix multiplications, providing roughly a 10× speed-up over NVIDIA's cuSOLVER routines on various large-scale matrices. In single-precision arithmetic with emulation on B200 GPUs, our approach maintains competitive accuracy while achieving up to a 2× speed-up. Consequently, for a 10,000 × 10,000 dense symmetric matrix, our method requires approximately 55 ms in half-precision and 400 ms in single-precision arithmetic on B200 GPUs. Integration into a first-order semidefinite programming solver confirms that our low-precision projections reliably yield solutions of moderate accuracy.

Citations

• The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm
• Local Linear Convergence of the Alternating Direction Method of Multipliers for Semidefinite Programming under Strict Complementarity
• Building Rome with Convex Optimization
• Global Contact-Rich Planning with Sparsity-Rich Semidefinite Relaxations
• Approximate Projections onto the Positive Semidefinite Cone Using Randomization
• Boosting projective methods for quantum process and detector tomography
• Fast and Certifiable Trajectory Optimization
• Structured Channel Covariance Estimation from Limited Samples for Large Antenna Arrays
• An Inexact Projected Gradient Method with Rounding and Lifting by Nonlinear Programming for Solving Rank-One Semidefinite Relaxation of Polynomial Optimization
• Exploiting Low-Rank Structure in Semidefinite Programming by Approximate Operator Splitting
• SDPNAL+: A Majorized Semismooth Newton-CG Augmented Lagrangian Method for Semidefinite Programming with Nonnegative Constraints
• Spectral Operators of Matrices
• Projection methods in conic optimization
• Toward the Optimal Preconditioned Eigensolver: Locally Optimal Block Preconditioned Conjugate Gradient Method
• Rational approximation to | x| .

Related

• Approximate Projections onto the Positive Semidefinite Cone Using Randomization
• Accelerating Low-Rank Factorization-Based Semidefinite Programming Algorithms on GPU
• Projections onto Spectral Matrix Cones
• Block Factor-Width-Two Matrices in Semidefinite Programming
• Efficient algorithms for computing rank-revealing factorizations on a GPU