In one of his lectures, Uri Feige described semidefinite programming (SDP) as

... an algorithmic technique that extends both linear programming and spectral algorithms.

I know the basic definition of SDP and understand it as linear programming extended by the possibility of saying "take these variables, arrange them into a matrix. Now, the matrix has to be positive semidefinite". Is this interpretation correct/useful? How is this an extension of spectral algorithms?

  • $\begingroup$ What is a spectral algorithm? $\endgroup$
    – Turbo
    Commented Mar 16, 2019 at 8:46
  • $\begingroup$ An algorithm based on spectral graph theory. That is, the algorithm uses eigenvalues and eigenvectors of matrices associated with the input graph (e.g. Laplace matrix, adjacency matrix...). I suppose that SDP only encompasses some spectral algorithms but which and how? $\endgroup$ Commented Mar 16, 2019 at 10:36
  • $\begingroup$ ' extends both linear programming and spectral algorithms' implies SDP encompasses all spectral algorithms. $\endgroup$
    – Turbo
    Commented Mar 16, 2019 at 10:49

1 Answer 1


This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the leading eigenvector of a symmetric matrix". So spectral algorithms that use the latter as a starting point can be interpreted as SDP rounding algorithm.

To see that SDPs can compute leading eigenvectors, let's take $A$ to be a symmetric matrix, and recall that the leading eigenvectors of $A$ are $\arg \max\{v^\top A v: \|v\|_2 = 1\}$. You can write $v^\top Av$ as $\mathrm{tr}(Avv^\top)$, and observe that $vv^\top$ is a PSD matrix of trace $1$. Then it's easy to check that the leading eigenvalue of $A$ is $\lambda_{\max} = \max\{\mathrm{tr}(AX): \mathrm{tr}(X) = 1, X \succeq 0\}$, which is the solution to an SDP, and every eigenvector of an optimal solution $X$ to this SDP will be a leading eigenvector of $A$. Similar tricks work for the minimum eigenvalue.

Let me give an example from spectral graph theory. Suppose $L$ is the normalized Laplacian of a graph. Then its smallest non-trivial eigenvalue is

$\lambda_2(L) = \min\{v^\top L v: \|v\|_2 = 1, \sum_i{\sqrt{d_i} v_i} = 0\},$

where $d_i$ is the degree of vertex $i$. (This is because $(\sqrt{d_1}, \ldots, \sqrt{d_n})$ is the eigenvector of eigenvalue $0$). You can rewrite this as the SDP

$\min\{\mathrm{tr}(LX): \mathrm{tr}(X) = 1, \mathrm{tr}(DX) = 0, X \succeq 0\}$,

where $D$ is the matrix with entries $D_{ij} = \sqrt{d_id_j}$. Cheeger's inequalities relate $\lambda_2$ to the conductance of the graph, and the proof of the inequalities can be seen as a rounding algorithm for the SDP.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.