#Finding projection of point onto k-plane in n dimensions

80 messages · Page 1 of 1 (latest)

pliant knot
#

Hi, just wondering if there's a simple way of finding a projection of a point onto a k-plane in n dimensions, for all k < n, k in Z+.
k-plane is defined as some starting point p0 + c1 (d1) + c2 (d2) ... + ck (dk)
my current method solves it in O(k^3) - intuitively there has to be a faster way (right?)

flat crescentBOT
#
  1. Do not ping the Moderators, unless someone is breaking the rules.
  2. Do not ping the Helper Moderators, unless there is a conflict between helpers.
  3. Do not ping other members randomly for help.
  4. Ask your question and show the work you've done so far. If you've posted a screenshot of a question, specify which part you need help with.
  5. Wait patiently for a helper to come along.
  6. If the Helper has answered your question, remember to thank them with the Mathematics Ranks bot and close the thread with:

+close
Feel free to nominate the person for helper of the week in #helper-nominations
If you're happy with the help you got here, and the server overall, you can contribute financially as well:

soft sinew
# pliant knot Hi, just wondering if there's a simple way of finding a projection of a point on...

If we want to project a vector on a subspace, this could help: you orthogonalize the basis vectors of your subspace, then just sum the projections onto them.
https://math.stackexchange.com/a/112743

Mathematics Stack Exchange
How do I exactly project a vector onto a subspace?

I am trying to understand how - exactly - I go about projecting a vector onto a subspace.

Now, I know enough about linear algebra to know about projections, dot products, spans, etc etc, so I am not

#

Though, this only works for p0 = 0.

pliant knot
#

can just translate p0 to 0 and back after the projection I assume

soft sinew
#

If we want to project onto a linear manifold, the process should be relatively the same: just subtract p0 from both the vector and the subspace, then project, then add p0 back.

soft sinew
pliant knot
#

right, so apply some sort of gram-schmit method to the basis vectors to from an orthogonal basis set, project onto every basis vector and the sum of these projections should be the projection onto the k-plane?

soft sinew
#

Yeah.

pliant knot
#

formulation of the basis set aside, this should be O(k)?

soft sinew
#

Don't know, sorry.

#

I know Landau symbols, but I haven't studied complexity theory.

pliant knot
#

hmm

#

intuitively it should be I think, since you're calculating an extra projection for every k

soft sinew
#

What was your initial approach, by the way?

pliant knot
#

it was kinda scuffed

#

convex optimisation approach, minimise point p - (plane eq)

#

formulate simultaneous equations

#

k equations, k unknowns

soft sinew
#

Ah, I see.

pliant knot
#

matrix, invert, O(k^3)

#

very slow

soft sinew
#

Oh, yeah, that is definitely much slower.

pliant knot
#

yeah felt like it was a really primitive way of going about it

cerulean niche
#

You can find the normal vector to the plane, say d. Find d0 such that <d, d0>= -p0

pliant knot
#

so i understand the problem is trivial in cases where k = n-1 for instance, since there is only one normal vector

cerulean niche
#

If you have the plane equation, you already have d

pliant knot
#

but given the formulation of the plane equation, say k=150 and n = 300

cerulean niche
#

If you are looking for d0, just start from d and do a line search, it converges in one step

pliant knot
#

it means that the normal to the k-plane is another k-plane of dimensionality 150

cerulean niche
#

So O(n)

pliant knot
cerulean niche
pliant knot
pliant knot
#

np ty anyways

cerulean niche
#

The k < n part

pliant knot
#

yeah, couldn't find much documentation on it

soft sinew
#

You're welcome!
Also, now I've saved that math stackexchange post. Could be helpful in the future.

pliant knot
#

yeah, for sure

cerulean niche
#

But then can't you just trim n?

#

It sounds like any component after the k-th component is not useful

pliant knot
#

i was just missing the simple fact that the projection onto a k plane is the sum of the projections onto its k basis vectors

soft sinew
#

As long as they are orthogonal.

pliant knot
pliant knot
#

i'll look into it, thanks a lot

cerulean niche
pliant knot
#

not quite sure i follow sorry

cerulean niche
#

For any D, the map f(x) = Dx is linear

pliant knot
#

right, as is the definition of linearity

cerulean niche
#

And its kernel is just the kernel of D, which you are interested in

pliant knot
#

yeah

cerulean niche
#

For a specific matrix D

pliant knot
#

but that solve is quite slow right?

#

i'm not super well-versed in linalg,

#

but solving a n x n matrix, is O(n^3) right

#

hermitian properties aside

cerulean niche
#

k x n

pliant knot
#

my method involves formulating k equations for k unknowns

#

funnily enough its actually nearly independent of n

#

which means O(k^3) i think

cerulean niche
#

But doesn't the fact that you have k unknowns mean that you somehow trimmed the dimension in the first place?

pliant knot
#

maybe, i'll have a search through my derivation to see if I implied that anywhere

#

it's a bit long to put here so i won't ask you guys to do that haha

#

thanks a lot, it'll be a good thing to write about lol

#

i'll close the channel if there are no last words

#

thanks again for the help

#

+close

frigid domeBOT
# pliant knot +close
Please thank your Helpers before closing!

Please thank the helpers who assisted you by clicking the buttons below. You can thank each helper only once. Once you're done, click "Close Post" to close this thread.

frigid domeBOT
# frigid dome

Thank you for your feedback! ARIMA(1,0,1)(2,1,1)_[12] has been awarded 1 helper_points. They now have 61 helper_points. They have 3 helper_points daily left for today.

cerulean niche
#

👍

frigid domeBOT
# frigid dome

Thank you for your feedback! LordDarpinger has been awarded 1 helper_points. They now have 900 helper_points. They have 3 helper_points daily left for today.

pliant knot
#

just a quick update, thought i'd let you guys know

#

apparently the gram-schmidt method is O(k^3) in this case too, so formulating the orthogonal basis set doesn't seem to be much faster than just calculating the projection by optimisation

#

great place for me to start searching though - and gives some confidence that maybe there isn't some constant-time solution I'm missing

#

thanks a lot