is (1) just an example or you actually have some problem which requires some sort of optimization over the space of "k-flats"? if you have such a problem, maybe you can exploit better the structure of it in order to simplify matters. for example, you can characterize the k-th largest eigenvalue of a hermitian matrix as the solution of a certain non-linear min-max problem in which the min is taken over the space of "k-flats" and the max is taken in that space (removing the origin, actually) that's the result of the Courant-Fischer Minimax Theorem, you can take a look at its statement here http://www.cs.tau.ac.il/~haima/gen_cf.pdf
my point is, exploiting the structure of your problem may lead to other more useful characterizations of the solution-set which wouldn't require you to actually try to find a representation for the set of k-flats... there are many different methods to compute eigenvalues...
Both of these are actual problems motivated by research ideas. #1 is like a regression problem: given points on a unit hypersphere centered at the origin, which k-dim "great circle" minimizes the residual sum of squares? The great circles correspond to the set of k-flats (aka "k-planes") through the origin (the circle is just the intersection of the flat and the sphere).
I don't see how eigenvalues might help here. Do you? I don't have a square matrix anywhere.
what do you mean by "residual sum of squares"? is it the sum of the squared distances to the k-flat? could it be the maximum of the squared distances? I will think about it...
did it... if you use the orthogonal distance (regular euclidean distance), it turns out that the solution is the same as that given by PCA... that's where an eigendecomposition solves this problem... ;)
just to fix notation, the solution (k-flat) corresponds to the vector space spanned by the eigenvectors associated to the k largest eigenvalues of the matrix \sum_i{x_i x_i^T}, x_i being the points on that sphere...
if you really want the proof, I guess I could take some time later to write it down for you or just meet me at UBC some day...
nice exercise, tough... I guess the geodesic distance would be way more complicated...
you're welcome... regarding the geodesic distance, it is simple to write down, but to optimize it I guess wouldn't be so simple... regarding convexity, I don't know what you could do since the sphere is not convex. I have some ideas to circumvent this but I'm not sure how useful they would be...
nop... but the closed ball is... I mean, a convex subset of the euclidean space... maybe we are adopting the same name for different things... let me make it clear... for me, the sphere is the set of x such that ||x||=1, and the closed ball is the set of x such that ||x|| <= 1 as a subset of the euclidean vector space (inheriting the usual addition and scalar multiplication), the sphere is not convex, but the closed ball is... are you ok with that?
This square matrix, is it n-by-n (where n is the dimension of the Euclidean space), or P-by-P (where P is the number of points)? I think the former. When you take all the eigenvectors, you end up with the original hypersphere.
my point is, exploiting the structure of your problem may lead to other more useful characterizations of the solution-set which wouldn't require you to actually try to find a representation for the set of k-flats... there are many different methods to compute eigenvalues...
a propósito, sou eu, Ives...
Reply
Both of these are actual problems motivated by research ideas. #1 is like a regression problem: given points on a unit hypersphere centered at the origin, which k-dim "great circle" minimizes the residual sum of squares? The great circles correspond to the set of k-flats (aka "k-planes") through the origin (the circle is just the intersection of the flat and the sphere).
I don't see how eigenvalues might help here. Do you? I don't have a square matrix anywhere.
Reply
Ives
Reply
yup. You could use either geodesic distance (ideal) or orthogonal distance. It probably doesn't matter which.
Reply
just to fix notation, the solution (k-flat) corresponds to the vector space spanned by the eigenvectors associated to the k largest eigenvalues of the matrix \sum_i{x_i x_i^T}, x_i being the points on that sphere...
if you really want the proof, I guess I could take some time later to write it down for you or just meet me at UBC some day...
nice exercise, tough... I guess the geodesic distance would be way more complicated...
cheers,
Ives
Reply
Reply
Ives
Reply
Reply
maybe we are adopting the same name for different things... let me make it clear...
for me, the sphere is the set of x such that ||x||=1, and the closed ball is the set of x such that ||x|| <= 1
as a subset of the euclidean vector space (inheriting the usual addition and scalar multiplication), the sphere is not convex, but the closed ball is...
are you ok with that?
cheers,
Ives
Reply
Reply
I think the former. When you take all the eigenvectors, you end up with the original hypersphere.
I now understand why PCA is the solution here.
Reply
Leave a comment