0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Nov 17 '14 at 21:34
  • $\begingroup$ Consider the case where eigeinvalues are rational. $\endgroup$
    – Daniel
    Nov 17 '14 at 21:41
  • $\begingroup$ It can happen of course. But it seems like a very special case. Do you have examples in mind? $\endgroup$ Nov 18 '14 at 1:11
  • $\begingroup$ 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? $\endgroup$
    – Daniel
    Nov 18 '14 at 1:35
1
$\begingroup$

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

$\endgroup$

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.