Timeline for Eigenvalues of $\operatorname{diag}({\bf v}) - {\bf v} {\bf v}^\top - \alpha({\bf v} - {\bf w})({\bf v} - {\bf w})^\top$
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 10, 2023 at 14:41 | comment | added | Rodrigo de Azevedo | @FedericoPoloni Yeah, this is overkill. Yet, it works even if the matrix is a linear combination of given matrices,, provided that it is symmetric. And it requires no knowledge of numerical linear algebra. I understand that numerical linear algebra is your field, but sometimes one has a problem to solve and does not have the time to take a course on NLA. In that case, better reduce the problem to LP, convex QP, SDP, etc, and let the solver handle it. The mathematical knowledge is in the solver, not the human user. | |
| Jun 10, 2023 at 12:52 | comment | added | Federico Poloni | Also, what is the complexity of solving this SDP? Does it beat $O(n^3)$ which would be the complexity of just computing the eigenvalues of a matrix $A$? | |
| Jun 9, 2023 at 17:40 | comment | added | Federico Poloni | You can remove the constraint by minimizing $\frac{x^TAx}{x^Tx}$, and convert it to the largest eigenvalue by shifting the matrix (by an amount that you can determine via norm estimates). Then there are various methods in linear algebra literature, the simplest one being the power method. But even minimizing the Rayleigh quotient with standard optimization techniques works fine, I have given similar problems to students as final projects in the past. | |
| Jun 9, 2023 at 15:29 | comment | added | Rodrigo de Azevedo | @FedericoPoloni But it's a non-convex QCQP. I can use a Lagrange multiplier and obtain $\bf (A - \mu I) x = 0$, but how do I find the minimal $\mu$? | |
| Jun 9, 2023 at 15:22 | comment | added | Federico Poloni | Yes! en.wikipedia.org/wiki/Rayleigh_quotient . | |
| Jun 9, 2023 at 14:59 | comment | added | Rodrigo de Azevedo | @FedericoPoloni Do you mean the following? $$\min_{ \| {\bf x} \|_2 = 1} {\bf x}^\top {\bf A} \, {\bf x}$$ | |
| Jun 9, 2023 at 14:22 | comment | added | Federico Poloni | It can also be found by minimizing the Rayleigh quotient, no need to use something more complicated. | |
| May 16, 2023 at 13:13 | history | answered | Rodrigo de Azevedo | CC BY-SA 4.0 |