Fast (1 + )-Approximation of the Lowner Extremal Matrices of High-Dimensional Symmetric Matrices

摘要

Let M_d(R) denote the space of square d x d matrices with real-valued coefficients, and Sym_d(R) = [S : 5 = S~T} ⊂ M_d(R) the matrix vector space~1 of symmetric matrices. A matrix P M_d(R) is said Symmetric Positive Definite (Bhatia 2009) (SPD, denoted by P ＞ 0) iff. ∀_x ≠ 0, x~T Px > 0 and only Symmetric Positive Semi-Definite~2 (SPSD, denoted by P ≥ 0) when we relax the strict inequality (∀_x, x~T P_x ≥ 0). Let Sym_d~+(R) = ｛X : X ≥ 0} ⊂ Sym_d(R) denote the space of positive semi-definite matrices, and Sym_d~(++)(R) - {X : X＞ 0} ⊂ Sym_d~+(R) denote the space of positive definite matrices. A matrix S Sym_d(R) is defined by D =d(d+1)/2 real coefficients, and so is a SPD or a SPSD matrix. Although Sym_d (R) is a vector space, the SPSD matrix space does not have the vector space structure but is rather an abstract pointed convex cone with apex the zero matrix 0 Sym_d~+(R) since ∀P_1, P2 Sym_d~+(R), ∀λ ≥ 0, P_1+λP_2 Sym_d~+(R). Symmetric matrices can be partially ordered using the Lowner ordering~3: P≥Q⇔P-Q≥0, P>Q⇔P-Q>0. When P ≥ Q, matrix P is said to dominate matrix Q, or equivalently that matrix Q is dominated by matrix P. Note that the difference of two SPSD matrices may not be a SPSD matrix.~4 A non-SPSD symmetric matrix S can be dominated by a SPSD matrix P when P - S > 0.~5.