# How is SDP an extension of spectral algorithms?

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?

• What is a spectral algorithm? Commented Mar 16, 2019 at 8:46
• 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? Commented Mar 16, 2019 at 10:36
• ' extends both linear programming and spectral algorithms' implies SDP encompasses all spectral algorithms. Commented Mar 16, 2019 at 10:49

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.