<p>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.</p>

<p>To see that SDPs can compute leading eigenvectors, let's take <span class="math-container">$A$</span> to be a symmetric matrix, and <a href="https://en.wikipedia.org/wiki/Min-max_theorem" rel="noreferrer">recall</a> that the leading eigenvectors of <span class="math-container">$A$</span> are <span class="math-container">$\arg \max\{v^\top A v: \|v\|_2 = 1\}$</span>. You can write <span class="math-container">$v^\top Av$</span> as <span class="math-container">$\mathrm{tr}(Avv^\top)$</span>, and observe that <span class="math-container">$vv^\top$</span> is a PSD matrix of trace <span class="math-container">$1$</span>. Then it's easy to check that the leading eigenvalue of <span class="math-container">$A$</span> is <span class="math-container">$\lambda_{\max} = \max\{\mathrm{tr}(AX): \mathrm{tr}(X) = 1, X \succeq 0\}$</span>, which is the solution to an SDP, and every eigenvector of an optimal solution <span class="math-container">$X$</span> to this SDP will be a leading eigenvector of <span class="math-container">$A$</span>. Similar tricks work for the minimum eigenvalue. </p>

<p>Let me give an example from spectral graph theory. Suppose <span class="math-container">$L$</span> is the normalized Laplacian of a graph. Then its smallest non-trivial eigenvalue is </p>

<p><span class="math-container">$\lambda_2(L) = \min\{v^\top L v: \|v\|_2 = 1, \sum_i{\sqrt{d_i} v_i} = 0\},$</span></p>

<p>where <span class="math-container">$d_i$</span> is the degree of vertex <span class="math-container">$i$</span>. (This is because <span class="math-container">$(\sqrt{d_1}, \ldots, \sqrt{d_n})$</span> is the eigenvector of eigenvalue <span class="math-container">$0$</span>). You can rewrite this as the SDP</p>

<p><span class="math-container">$\min\{\mathrm{tr}(LX): \mathrm{tr}(X) = 1, \mathrm{tr}(DX) = 0, X \succeq 0\}$</span>, </p>

<p>where <span class="math-container">$D$</span> is the matrix with entries <span class="math-container">$D_{ij} = \sqrt{d_id_j}$</span>. <a href="http://www.cs.yale.edu/homes/spielman/561/lect06-15.pdf" rel="noreferrer">Cheeger's inequalities</a> relate <span class="math-container">$\lambda_2$</span> to the conductance of the graph, and the proof of the inequalities can be seen as a rounding algorithm for the SDP.</p>

CC BY-SA 4.0
2019-03-16T15:19:46.107Z
2019-03-16T18:19:00.890Z
2019-03-16T18:19:00.890Z
Sasho Nikolov
<p>In one of his lectures, Uri Feige described semidefinite programming (SDP) as </p>

<blockquote>
  <p>... an algorithmic technique that extends both linear programming and spectral algorithms.</p>
</blockquote>

<p>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?</p>

CC BY-SA 4.0
2019-03-16T08:46:29.127Z
What is a spectral algorithm?
Turbo
CC BY-SA 4.0
2019-03-16T10:36:01.377Z
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?
user2316602
CC BY-SA 4.0
2019-03-16T10:49:27.403Z
' extends both linear programming and spectral algorithms' implies SDP encompasses all spectral algorithms.
Turbo
<ds.algorithms><graph-algorithms><linear-programming><spectral-graph-theory><semidefinite-programming>
How is SDP an extension of spectral algorithms?
user2316602
# How is SDP an extension of spectral algorithms?

(Asked by: username_0 on 2019-03-15)

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?

**Tags:** ds.algorithms, graph-algorithms, linear-programming, spectral-graph-theory, semidefinite-programming
> **Comments:**
> **username_1**: What is a spectral algorithm?  
> **username_0**: 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?  
> **username_1**: ' extends both linear programming and spectral algorithms' implies SDP encompasses all spectral algorithms.  

---

## 1 answers

### Answer by username_2 on 2019-03-16. Score: 6 | Accepted answer

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](https://en.wikipedia.org/wiki/Min-max_theorem) 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](http://www.cs.yale.edu/homes/spielman/561/lect06-15.pdf) 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.


---

