# Spectral methods with linear programming

Is it possible to model and solve some fundamental spectral methods (say Singular-Value Decomposition) with (Integer?) Linear Programming?

Update: say you want to do SVD. Can you model it as a linear object with linear constraints?

The problem the other way around is also interesting. Say you have an LP. Can you solve it with SVD?

• Basically this cannot work: usually LP or ILP calculations are carried out over the field generated by the entries of the matrix, and so you stay in the rationals, but for SVD you need the actual eigenvalues which are likely not rational. Nov 17 '14 at 21:34
• Consider the case where eigeinvalues are rational. Nov 17 '14 at 21:41
• It can happen of course. But it seems like a very special case. Do you have examples in mind? Nov 18 '14 at 1:11
• Actually I don't have any problem in mind. But say you want to do SVD. Can you model it as a linear object with linear constraints? Nov 18 '14 at 1:35

## 1 Answer

I do not think that this can be done with linear programming. However, there is a generalisation of linear programming called semidefinite programming which allows you to do this. I think you should look at the answer to my question regarding this connection.

https://cstheory.stackexchange.com/questions/42526/how-is-sdp-an-extension-of-spectral-algorithms