Another class of approaches for efficiency improvement is to (equivalently or approximately) decompose a large PSD matrix into the sum of smaller PSD matrices that are easier to handle [1]}.
Specifically, one can try to decompose \(X=\sum _{i=1}^{t} Q_i\) , where \(Q_i \succeq 0\)  are nonzero
only on a certain (and, ideally, small) principal submatrix. When \(X\)  has a special chordal sparsity pattern, such a decomposition is equivalent [1]}, [3]}, [4]}. In general, the decomposition above gives an inner approximation of the PSD cone \(\mathbb {S}^n_+\) . One widely used strategy is so-called scaled-diagonally dominant (SDD) matrices , where each \(Q_i\)  only involves a \(2 \times 2\)  nonzero principle matrix that is equivalent to a second-order cone constraint. Second-order cone programs (SOCPs) admit much more efficient algorithms than SDPs. This scalability feature is one main motivation in the recent studies [5]}, [6]}, [7]}, [8]}, [9]}, [10]}. In particular, this idea has been extensively used in the context of sum-of-squares optimization [5]}.
While the SDD approximation brings considerable computational efficiency in solving (), the solution might be very conservative [5]}, [1]}. Several iterative methods have been further proposed to improve solution quality, such as adding linear cuts or second-order cuts [7]}, [8]}, [6]}, and
basis pursuit searching [9]}, [10]}.
These methods [7]}, [6]}, [8]}, [9]}, [10]} solves a linear program (LP) or an SOCP at each iteration, but may require many iterations to get a reasonable good solution (if possible) .
