Timeline for I want a smooth orthogonalization process
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 27 at 17:22 | comment | added | Jabby | Thanks @VítTuček. It's strange that this result seems to not be known very well (as the OP of the stackexchange page also notes). For example, I was reading this recent 2023 preprint that states that 'Unlike balanced OPPs, there is no closed-form solution to the other classes of Procrustes problems known and therefore an algorithmic approach is required'. In table 2 of the same paper it shows SVD as only being a solution for the balanced case. | |
| Sep 27 at 11:21 | comment | added | Vít Tuček | @Jabby For symmetric matrices, the unit norm eigenvectors for simple eigenvalues are defined only up to multiplication by -1 (or $e^\imath \phi$ in the complex case). For eigenvalue of multiplicty $k$ we even have a freedom of $O(k)$ (or $U(k)$). Please note that the math.stackexchange page found by PedroLauridsenRibeiro actually contains references and proofs for the claim that $UV^T$ is the closest point on the Stiefel manifold to the matrix $U\Sigma V^T$. | |
| Sep 27 at 5:07 | comment | added | Pedro Lauridsen Ribeiro | Hmm... According to what seems to be the state of the art in understanding the problem (called the "unbalanced Procrustes problem" in the numerical analysis literature), it certainly appears so - check e.g. L. Eldén, H. Park, A Procrustes Problem on the Stiefel Manifold, Numer. Math. 82 (1999) 599-619 and Z. Zhang, Y. Qiu, K. Du, Conditions for Optimal Solutions of Unbalanced Procrustes Problem on Stiefel Manifold, J. Comput. Math. 25 (2007) 661-671. See also math.stackexchange.com/questions/4492668/… | |
| Sep 26 at 22:52 | comment | added | Jabby | I see. That makes sense. Thank you. Regarding your nearest orthogonal matrix suggestion, the wikipedia page suggests that it is only valid for SVD on square matrices (I have a rectangular matrix that represents a subspace). This page suggests that the analogous optimization on the stiefel manifold has no known analytic solution. Is this correct? | |
| Sep 26 at 19:46 | comment | added | Pedro Lauridsen Ribeiro | Moreover, there is no single orthonormal basis of eigenvectors of an eigenspace of a linear map since every vector in the eigenspace is an eigenvector with the same eigenvalue by definition. This of course applies to the vector subspace associated to an orthogonal projection $P$ ( = eigenspace of $P$ with eigenvalue $1$). In other words, even though the map $$k\text{-dimensional subspace } W\mapsto P_W=\text{orthogonal projection associated to }W$$ is well defined, it does not select a single orthonormal basis for any $W$ at all. | |
| Sep 26 at 19:35 | comment | added | Pedro Lauridsen Ribeiro | I fail to understand what you're pointing at. Which map are you referring to? If you're referring to the orthogonal projection $P$ associated to a vector subspace, it's actually independent of the orthonormal basis chosen, even though you can certainly write the former in terms of the latter. Moreover, any such $P$ will act as the identity map in its image ( = vector subspace associated to $P$), so it cannot turn a non-orthogonal basis of that subspace into an orthonormal one since basis vectors of the subspace are unchanged by the action of $P$. | |
| Sep 26 at 15:06 | comment | added | Jabby | One solution that avoids the axis flipping is the following. Each subspace has a unique representation as an orthogonal projector $P = UU^T$, where $U$ is an orthonormal basis of the subspace (e.g. obtained as the right singular vectors of the matrix $B$). The eigenvectors of $P$ can then be used as my orthonormal basis. By abstracting away from basis vectors to their subspace, axis flipping can be avoided. Is this the kind of map I requested here? Does it have discontinuities? | |
| Sep 25 at 20:20 | comment | added | Pedro Lauridsen Ribeiro | Just a question: is your original example actually encountered in the applications you are interested in? More precisely, do you actually expect there to occasionally flip the orientation of the basis due to e.g. rounding errors, as Ryan Budney suggests in his comment to the OP? If so, SVD methods still seem to be a good choice because they deal well with degeneracy problems such as the one encountered here thanks in large part to the distance minimization feature pointed in Vit's answer above. | |
| Sep 25 at 20:04 | comment | added | Jabby | I should add that the $UV^T$ solution still suffers from the type of issue illustrated in my original example: $UV^T$ is very different if my second vector is a counterclockwise vs. clockwise rotation of my first vector. | |
| Sep 25 at 19:43 | comment | added | Pedro Lauridsen Ribeiro | As far as I know, SVD methods are somewhat preferred in machine learning applications, even as just part of more sophisticated methods. | |
| Sep 25 at 16:40 | comment | added | Jabby | I find the $UV^T$ solution very attractive. For reasons I wont go into, the right singular vectors $V$ was the solution I was originally working with, but it wasn't ideal because 1) the sign of the right singular vectors is arbitrary and so can flip, and 2) the ordering of the right singular vectors is based on the ranking of the singular values and so can also flip as the singular values change. Both of these issues, which can cause discontinuities in my basis, are resolved by using $UV^T$, as the signs and orderings of the left/right singular vectors are paired and cancel each other out. | |
| Sep 25 at 16:15 | comment | added | Vít Tuček | @LSpice I missed that comment, sorry. Of course, smoothness is a local property. I just wanted to explain that to the OP. | |
| Sep 25 at 15:33 | comment | added | tomasz | Smoothness is a local property though. As others have noted, what fails is not smoothness, but uniform continuity. | |
| Sep 25 at 15:21 | history | edited | LSpice | CC BY-SA 4.0 |
Link to @TomGoodwillie's answer
|
| Sep 25 at 15:16 | comment | added | LSpice | I am confused by the statement that Gram–Schmidt is only locally smooth—as you mention, the comments (for example, by @PedroLauridsenRibeiro) discuss that the problem in the statement is not a failure of smoothness, but just a manifestation of moving from one connected component of the domain to another. | |
| Sep 25 at 14:28 | history | answered | Vít Tuček | CC BY-SA 4.0 |