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?
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.
