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$
    – Mr.
    Mar 16 '19 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$ Mar 16 '19 at 10:36
  • $\begingroup$ ' extends both linear programming and spectral algorithms' implies SDP encompasses all spectral algorithms. $\endgroup$
    – Mr.
    Mar 16 '19 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.