Approximate Projections onto the Positive Semidefinite Cone Using Randomization

This paper presents two novel algorithms for approximately projecting symmetric matrices onto the Positive Semidefinite (PSD) cone using Randomized Numerical Linear Algebra (RNLA). Classical PSD projection methods rely on full-rank deterministic eigen-decomposition, which can be computationally prohibitive for large-scale problems. Our approach leverages RNLA to construct low-rank matrix approximations before projection, significantly reducing the required numerical resources. The first algorithm utilizes random sampling to generate a low-rank approximation, followed by a standard eigen-decomposition on this smaller matrix. The second algorithm enhances this process by introducing a scaling approach that aligns the leading-order singular values with the positive eigenvalues, ensuring that the low-rank approximation captures the essential information about the positive eigenvalues for PSD projection. Both methods offer a trade-off between accuracy and computational speed, supported by probabilistic error bounds. To further demonstrate the practical benefits of our approach, we integrate the randomized projection methods into a first-order Semi-Definite Programming (SDP) solver. Numerical experiments, including those on SDPs derived from Sum-of-Squares (SOS) programming problems, validate the effectiveness of our method, especially for problems that are infeasible with traditional deterministic methods.