Question

Here is my proof: http://mathb.in/86533
doing A^T b = A^T A x suffices when dealing with real vectors to get a projection. In the complex case this method gives me weird results using my proof. How do I project complex vectors and how do I prove it?

Answer 1

\[\begin{equation} \begin{Vmatrix}c\end{Vmatrix}^2 = \begin{Vmatrix}a-b\end{Vmatrix}^2 = \begin{Vmatrix}a\end{Vmatrix}^2 + \begin{Vmatrix}b\end{Vmatrix}^2 -2 \begin{Vmatrix}a\end{Vmatrix} \begin{Vmatrix}b\end{Vmatrix} \cos(\theta) \end{equation} \]

Answer 2

\[\begin{equation} \begin{Vmatrix}a-b\end{Vmatrix}^2 = \langle c,c \rangle = \\ \sum_{k=0}^n \overline{c_k} c_k = \sum_{k=0}^n \Bigg( \Big( \Re(c_k)-\Im(c_k)i \Big) \Big( \Re(c_k)+\Im(c_k)i \Big) \Bigg) = \\ \sum_{k=0}^n \Bigg( \Big( \Re(c_k)^2 -\Re(c_k)\Im(c_k)i +\Re(c_k)\Im(c_k)i -\Im(c_k)^2i^2 \Big) \Bigg) = \\ \sum_{k=0}^n \Bigg( \Re(c_k)^2 + \Im(c_k)^2 \Bigg) = \sum_{k=0}^n \Bigg( \Re(a_k-b_k)^2 + \Im(a_k-b_k)^2 \Bigg) \end{equation}\]

Answer 3

\[\begin{equation} \Re(a_k-b_k)^2 = \Big( \Re(a_k)-\Re(b_k) \Big) \Big( \Re(a_k)-\Re(b_k) \Big) = \\ \Re(a_k)^2 -2\Re(a_k)\Re(b_k) + \Re(b_k)^2 \\ \Im(a_k-b_k)^2 = \Big( \Im(a_k)-\Im(b_k) \Big) \Big( \Im(a_k)-\Im(b_k) \Big) = \\ \Im(a_k)^2 -2\Im(a_k)\Im(b_k) + \Im(b_k)^2 \end{equation}\]

Answer 4

\[\begin{equation} \sum_{k=0}^n \Bigg( \Re(a_k-b_k)^2 + \Im(a_k-b_k)^2 \Bigg) = \\ \sum_{k=0}^n \Bigg( \Big( \Re(a_k)^2+\Im(a_k)^2 \Big) + \Big( \Re(b_k)^2+\Im(b_k)^2 \Big) -2 \Big( \Re(a_k)\Re(b_k) + \Im(a_k)\Im(b_k) \Big) \Bigg) = \\ \langle a,a \rangle + \langle b,b \rangle -2 \sum_{k=0}^n \Bigg( \Re(a_k)\Re(b_k) + \Im(a_k)\Im(b_k) \Bigg) = \\ \begin{Vmatrix}a\end{Vmatrix}^2 + \begin{Vmatrix}b\end{Vmatrix}^2 -2 \sum_{k=0}^n \Bigg( \Re(a_k)\Re(b_k) + \Im(a_k)\Im(b_k) \Bigg) = \\ \begin{Vmatrix}a\end{Vmatrix}^2 + \begin{Vmatrix}b\end{Vmatrix}^2 -2 \begin{Vmatrix}a\end{Vmatrix} \begin{Vmatrix}b\end{Vmatrix} \cos(\theta) \end{equation}\]

Answer 5

\[\begin{equation} \sum_{k=0}^n \Bigg( \Re(a_k)\Re(b_k) + \Im(a_k)\Im(b_k) \Bigg) = \begin{Vmatrix}a\end{Vmatrix} \begin{Vmatrix}b\end{Vmatrix} \cos(\theta) \end{equation}\]

Answer 6

Well for starters I believe the projection formula for projecting \(\vec a\) on \(\vec b\) would be, well first this will be the projection operator:

\[P = \frac{\vec b \vec b^\dagger }{\vec b^\dagger \vec b}\]
Then the projection will end up being:

\[P\vec a = \frac{\vec b^\dagger \vec a}{\vec b^\dagger \vec b} \vec b\]

It sorta sounds like you're not dividing by the magnitude of the vector you're trying to project on, you're only doing the dot product. So maybe in terms of more familiar notation to you, the magnitude of the projection of a onto b is:

\[|a| \cos \theta\]

the direction being
\[\frac{b}{|b|}\]

but I think you know this already so maybe you just left out a little bit there, I'm not sure I am thinking about this though, since how the dot product works for complex numbers seems like it might have a few issues with how the terms combine.

Answer 7

(b-Ax) should be perpendicular/orthogonal to the column space of A in order to get the closest point to b possible. My proof implies that is the case when A @ (b-Ax) = 0, where @ denotes we should take the vectors of A and apply the formula we ended up with at the end of my proof to (b-AX)

Answer 8

I'm talking about more general cases. what you're saying is correct, but it only considers projecting 1 vector onto another vector. I would like to project a vector onto a set of vectors stored in the columns of A so to speak

Answer 9

Sure seems reasonable I just don't really fully know what you're talking about apparently. What is b, A, and x according to you?

Answer 10

b is a complex vector. (the values of b are arbitrary, but we assume we know these values)
A is a complex matrix. (the values of A are arbitrary, but we assume we know these values)
x is a complex vector. (the one we're trying to solve)

Answer 11

I think I'm missing the point, if you know b and A, and you want x to be as close to b as possible why not just pick x to be b itself?

Answer 12

because b can lie outside of the reach of A.
Ax = b can't always be solved, but A^T b = A^T A x can. (in the real case)

Answer 13

\[\left[\begin{matrix}1 & 0 \\ 0 & 0\end{matrix}\right] x = \left(\begin{matrix}1 \\ 1\end{matrix}\right)\]

Answer 14

this example clearly shows what i mean

Answer 15

there is no possible way to multply A with some arbitrary x, such that Ax = b

Answer 16

but we can try to multiply A with some arbitrary x such that Ax = b projected onto A

Answer 17

so when we do (b-Ax) we should end up with a vector that is perpendicular to A

Answer 18

this ensures that x multiplied by A brings it as close to b as possible

Answer 19

I would like to generalize this concept to the complex case

Answer 20

Wait, you would like to solve Ax=b but it has no solution. So instead you would like to solve A^TAx=A^Tb since this supposedly always has a solution?

since A^TA is necessarily a square matrix, is it possible that it has an inverse since it is normal?

\[x = (A^TA)^{-1}A^T b\]

I feel like you're assuming I know more about the problem than you've told me.

Answer 21

Can you like, start from the beginning? Is this a problem from your own mind or is there some problem wording somewhere you can type out? I really don't know what you're trying to do and what you're trying to work with/from. It's like you're in the middle of something, so it doesn't make sense lol

Answer 22

hehe yeah sorry :P

Answer 23

It's hard for me to explain

Answer 24

but i'll try

Answer 25

haha ok that's fine as long as you're willing to work with me here we're good xD

Answer 26

ok so basically, it all started when I was introduced to matrices an vectors...
I came from a place where i knew how to solve y=ax + b
So when i learned about matrices I was wondering how would one solve this equation, but with matrices and vectors

Answer 27

So I did some research and came to the conclusion that not all matrices could be solved, like the example above.

Answer 28

then I thought ok... but what would be as close to a satisfying answer as possible in those cases

Answer 29

I came to the conclusion that Ax has to be as close to b as possible

Answer 30

aha cool yeah that's interesting, so I can see how that's leading you towards projections, but complex vectors are like kinda fishy cause each component is like a 2D vector which is weird I guess that's part of the problem maybe

Answer 31

well... when is Ax as close to b as possible? right, when Ax = b projected onto A

Answer 32

yeah it's hard :(

Answer 33

especially hard to visualize :(

Answer 34

so now we know what we're looking for... we can start generalizing concepts we know

Answer 35

oi yeah I see what you mean now about 'projecting onto the matrix' like finding the subspace of the matrix where it does exist, like in a way you need to project b onto the space spanned by A I guess

Answer 36

we know that in the real case A^T b = A^T A x can be solved (I saw that proof on khan academy)

Answer 37

yeah exactly! :D

Answer 38

so I started to expand the khan academy proof to the complex case

Answer 39

interesting I'm not too familiar with that, can you link me to it I'll check it out real fast

Answer 40

hmmm I don't know the link, let me look it up

Answer 41

Ah nice, I've bookmarked it: https://www.khanacademy.org/math/linear-algebra/alternate-bases/orthogonal-projections/v/lin-alg-a-projection-onto-a-subspace-is-a-linear-transforma :D

Answer 42

I can kinda see why it might be true, since if you imagine the column vectors filling A then A^Tb is how you'd set up the dot product of every column vector with A with b.

Answer 43

yeah exactly

Answer 44

the only problem is.... the dot product works weird in the complex case to say the least

Answer 45

So far it looks like the khan academy case is different, since the columns of A form a basis for the subspace while your example you have a zero vector in there so it doesn't form a basis, I can explain more if you don't see what I mean there

Answer 46

but my proof shows how it can be generalized to the complex case, only applying that proof ends up with weird results, so either my proof is wrong, or I'm assuming something which I shouldn't (I guess it's the latter, but I can't figure out what it is... to me the proof seems flawless)

Answer 47

Well the end case of your proof looks like you are getting a purely real number, but I think the dot product of complex vectors is in general not real unless it's a vector with itself. I read it earlier and it seemed fine but maybe I didn't read it well enough I wasn't really sure what you were doing but the individual steps looked good

Answer 48

yeah in the case I gave above we have multiple answers for x... which can be calculated by taking one random answer and adding the Nullspace of A^T A

Answer 49

yes I was expecting to end up with complex results, but my proof seems flawless and gives real numbers, which is weird :S

Answer 50

ok here we go at 11:54 or a little before that he says "A whose columns are linearly independent implies \(A^TA\) is always invertible"

in the cases you're looking at it's not the case I think, or at least for the example you chose, so this might not be the route to get the entirely general sorta solution you want but I can see this maybe being a way to get partially the answer you are looking for.

Answer 51

yeah I noticed that part of the video, but I can't think of any matrix where A^T b = A^T A x isn't solvable, so I guess he made a mistake by saying that in the video... or at least... it's to ensure that x can be solved and has only 1 answer, but I want to be able to "solve" it even when there are multiple answers

Answer 52

gotcha, you're wanting to generalize more than this stuff hmm

Answer 53

what I mean is... it's impossible for x to have no solutions when the columns of A are linear dependent

Answer 54

Hehe I know it's complicating stuff, but I just want total freedom :)... feed the algorithm any complex A and any complex b and spit out some x plus the span of the Nullspace

Answer 55

well ok for your example up there \[\left[\begin{matrix}1 & 0 \\ 0 & 0\end{matrix}\right] x = \left(\begin{matrix}1 \\ 1\end{matrix}\right)\]

it seems we can really use any choice here of free variable:

\[x = \begin{pmatrix} 1 \\ k\end{pmatrix}\]

Or, well, what are the solutions you're expecting, since I can imagine a few different things that could be considered "the best choice of x"

Answer 56

\[\left(\begin{matrix}1 \\ k\end{matrix}\right)\] is precisely the answer I want for this example

Answer 57

Aha, so the number of free variables in your answer is equal to the rank of the null space of A I guess that's the way of saying it, kinda rusty on the terminology here

Answer 58

hmmm lambda doesn't seem to work

Answer 59

I guess really your solution is not a vector, it's a space, since

\[x=\left(\begin{matrix}1 \\ 0\end{matrix}\right)+k\left(\begin{matrix}0 \\ 1\end{matrix}\right)\]

Looks like we might be able to see something by looking at the vector when we factor out the weights as a vector:

\[x= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ k \end{pmatrix} \]

Ok nevermind that just got us the identity matrix nothing too interesting here haha hmmm I was thinking in general though you might not have such straightforward dependence between your free variables and the basis vectors.

Answer 60

ohw well... the most precise answer for x would be \[x = \left(\begin{matrix}1 \\ 0\end{matrix}\right) + L\left(\begin{matrix}0 \\ 1\end{matrix}\right)\]

Where L = lambda

Answer 61

we're on the same wavelength :)

Answer 62

haha yeah. It seems like the end result will be that the null space will be the answer + Ab now that I think of it.

Answer 63

Well ok no that's not right, the Ab part is wrong. It's like really each component is minimized, for some variable x... Arg...

Answer 64

https://www.youtube.com/watch?v=cTyNpXB92bQ&feature=youtu.be&t=508
this is the key part in that video

Answer 65

Yeah you just beat me to it I was kinda heading this route, thinking about projecting onto the null space haha

Answer 66

this says... ohw hey... as long as (b-Ax) and the column vectors are perpendicular, we'll end up with x being solvable...

Answer 67

Buuut he's saying the columns of A are linearly independent so we can't use that directly we gotta think a little more how to make it work I think

Answer 68

and since my proof says that is the case when A^T @ (b-Ax) = 0, where i define @ as applying the sum(real*real + imaginary+imaginary with each component of the row) thingy in my proof... we should end up with our answer... but we don't :(

Answer 69

The only reason why that would matter is if you only except x to have one single solution as far as I can tell, but since I except more answers it shouldn't be a problem... we just need to add the Nullspace as additional answers

Answer 70

accept*

Answer 71

correction: imaginary*imaginary

Answer 72

Ok how about this, if A is not filled with linearly independent vectors, we can find the null space and then we know there's some matrix so that this IS true:

\[(A+N)x = b\]

Then following with what they do;

\[(A+N)^T (A+N)x = (A+N)^Tb\]
\[x = [(A+N)^T (A+N)]^{-1}(A+N)^Tb\]

so now x is in terms of all these free variables that you found and are a part of your null space

Answer 73

Sorry \((A+N)x \ne b\) however when you multiply on the left by the transpose then it is true is what I meant.

Answer 74

oi I'll reexplain since I think I did that a bit poorly lol

What he does is uses a matrix A that has linearly independent columns, we don't so in order to make A linearly independent we find its null space and add it to it so that it will contain the space and is null space:

\[(A+N)x \ne b\]
However it's just the same as before, it's not solvable so we want the closest approximation, so basiaclly we run thruogh the same thing as they do except instead of with A we use A+N.

\[(A+N)^T (A+N)x = (A+N)^Tb\]
\[x = [(A+N)^T (A+N)]^{-1}(A+N)^Tb\]

so now x is in terms of all these free variables that you found and are a part of your null space

Answer 75

hmmm I understand what you're doing, but I don't see how that solves anything

Answer 76

let's take a very basic example

Answer 77

\[\left[\begin{matrix}1 \end{matrix}\right] x = \left(\begin{matrix}i \end{matrix}\right)\]

Answer 78

it's just generalizing the solution to things like this: \[\left[\begin{matrix}1 & 0 \\ 0 & 0\end{matrix}\right] x = \left(\begin{matrix}1 \\ 1\end{matrix}\right)\]
\[x = \begin{pmatrix} 1 \\ k\end{pmatrix}\]

But it doesn't cover the complex case at all.

Answer 79

the nullspace of [1] = 0

Answer 80

so we'll end up with 1x=b

Answer 81

ah ok

Answer 82

yeah but the problem lies in the complex case :P the real case I've kinda solved already

Answer 83

Haha I don't know if I agree with you but at any rate I'm willing to look at the complex case. I don't really know how your proof of the dot product with complex vectors is supposed to apply actually

Answer 84

let's take \[\left(\begin{matrix}3+4i \\ 1+2i\end{matrix}\right) @ \left(\begin{matrix}2+2i \\ 6+7i\end{matrix}\right)\] as an example

Answer 85

this would give us 3*2 + 4*2 + 1*6 + 2*7 = 6+8+6+14 = 34

Answer 86

to be clear the @ symbol I came up with... since this definition doesn't really exist

Answer 87

and there's probably good reasons why it doesn't exist, but I can't figure out the flaw in the proof

Answer 88

Yeah, usually the dot product for complex vectors is defined to have the complex conjugate and transpose, so for instance:
\[\left(\begin{matrix}3+4i \\ 1+2i\end{matrix}\right) ^\dagger \left(\begin{matrix}2+2i \\ 6+7i\end{matrix}\right)=\left(\begin{matrix}3-4i &1-2i\end{matrix}\right) \left(\begin{matrix}2+2i \\ 6+7i\end{matrix}\right)\]

and for this, you are just doing usual matrix multiplication here, so you have:

\[=(3-4i)(2+2i)+(1-2i)(6+7i)\]

that would be the value of the dot product in the complex case when you work it out. It's a little clearer if you dot a vector with itself that it gives the length squared since for complex numbers, you have:

\[z=x+iy\]
\[z^* z = x^2+y^2 = |z|^2\]

Answer 89

yeah I'm aware of that definition, but I've searched all over the internet and couldn't find anything that proves this is the right definition... it just states it is right by definition, but my @ definition can actually be proven... basically my @ definition is the Real part of <a,b>

Answer 90

my @ definition makes geometrical sense, while the "correct" definition doesn't, it doesn't even make algebraic sense

Answer 91

so basically what I'm looking for is the inner product equivalence of my proof that makes sense when applying it to the Ax = b problem

Answer 92

my gut tells me that the solution to this problem in the complex case is:
conj(A^T) b = conj(A^T) A x... but I would like to know for sure by proving that this is correct

Answer 93

the same way as we have proven it for the real case

Answer 94

Do you know what I mean?

Answer 95

the steps in between are:
1. (b-Ax) has to be orthogonal to A...
2. ohw ok well... that's the same as saying: conj(A^T) (b-Ax) = 0 + 0i
3. now let's distribute the conj(A^T)... conj(A^T) b - conj(A^T) A x = 0 + 0j
4. move to the right gives: conj(A^T) b = conj(A^T) A x
5. and thus (conj(A^T) A)^-1 conj(A^T) b = x

the only problem is... I don't understand how step 2. can be correct, since my proof implies that A @ (b-Ax) = 0 + 0i

Answer 96

also, wikipedia: https://en.wikipedia.org/wiki/Dot_product#Complex_vectors states that \[\Re(a \cdot d) = ||a|| ||b || \cos(\theta)\]

which implies that (\[\Re(conj(A^T) b - conj(A^T) A x) = \Re(0 + \lambda i)\]

this confuses me even more :(

Answer 97

also, wikipedia: https://en.wikipedia.org/wiki/Dot_product#Complex_vectors states that \[\Re(a \cdot d) = ||a|| ||b || \cos(\theta)\]

which implies that (\[\Re(conj(A^T) b - conj(A^T) A x) = \Re(0 + \lambda i)\]

this confuses me even more :(