Computing a Positive Semidefinite Arrowhead Matrix Closest to Noisy Data

Arrowhead matrices, consisting of a diagonal block augmented by a single dense row and column, arise naturally in a wide range of applications in numerical linear algebra, physics, statistics, optimization, and network analysis. In many of these settings, positive semidefiniteness is a fundamental requirement, for example in covariance estimation, stability analysis, and energy-based models. Motivated by these applications, we study the problem of computing the nearest positive semidefinite arrowhead matrix to a given data matrix in the Frobenius norm. The data matrix may be noisy or indefinite and is not necessarily symmetric, which presents additional challenges compared to classical nearest positive semidefinite approximation problems. We formulate the problem as a convex optimization problem with both structural and semidefiniteness constraints and investigate several solution approaches. These include an alternating projection method, semidefinite programming formulations, and mixed semidefinite–second-order cone programming formulations that explicitly exploit the arrowhead structure. By leveraging this structure, we derive reduced formulations with significantly lower computational complexity. Numerical experiments on randomly generated matrices of orders up to n=1000 demonstrate that while projection-based and standard semidefinite programming methods are reliable, they become computationally expensive for large-scale problems. In contrast, the mixed second-order cone formulations exhibit excellent scalability, requiring substantially fewer iterations and dramatically reduced CPU time while maintaining comparable solution accuracy. These results highlight the effectiveness of structure-exploiting optimization formulations for large-scale nearest positive semidefinite arrowhead matrix approximation problems.