Dot Product of Streaming vectors

[zheng004]

Hi all,

Suppose we have vectors coming in order as A, B and then C (but A must be deleted before C comes in). Then how to get the dot product between A and C? It is allowed to store some calculations of A before deleting elements of A, for example, we could store norm of A, dot(A, B) and etc.

I tried to store (A + B) .^2, (A - B)^2, and then replace B with C, but failed. Please help!

 

[Buffu]

Hi all,

Suppose we have vectors coming in order as A, B and then C (but A must be deleted before C comes in). Then how to get the dot product between A and C? It is allowed to store some calculations of A before deleting elements of A, for example, we could store norm of A, dot(A, B) and etc.

I tried to store (A + B) .^2, (A - B)^2, and then replace B with C, but failed. Please help!

Store A in B and then dot B and C.

 

[zheng004]

Store A in B and then dot B and C.

Thanks for your reply, it is not allowed to store A in B as B will be used later. Actually, deleting A is to save space.

 

[Buffu]

Thanks for your reply, it is not allowed to store A in B as B will be used later. Actually, deleting A is to save space.

In your post you said you are trying to store (A-B)^2 and (A+B)^2. Where are you storing these if space is limited ?

 

[zheng004]

In your post you said you are trying to store (A-B)^2 and (A+B)^2. Where are you storing these if space is limited ?

Sorry, should be square of sum, i.e. store (a_1 + a_2 + ... + a_n - b_1 - b_2 - ... - b_n)^2 and (a_1 + a_2 + ... + a_n + b_1 + b_2 - ... + b_n)^2. These are the values so easy to store.

Very appreciated if you can help. Thanks.

 

[Buffu]

Sorry, should be square of sum, i.e. store (a_1 + a_2 + ... + a_n - b_1 - b_2 - ... - b_n)^2 and (a_1 + a_2 + ... + a_n + b_1 + b_2 - ... + b_n)^2. These are the values so easy to store.

Very appreciated if you can help. Thanks.

So you can store 2 floats at max ?

 

[jedishrfu]

Csn you provide some context here? This seems like an arbitrary constraint.

 

[zheng004]

So you can store 2 floats at max ?

We can store any value as long as using limited space.

 

[zheng004]

Csn you provide some context here? This seems like an arbitrary constraint.

Ok, here is the context. The incoming large vectors in order are A, B, C. But spaces are limited, to receive vector C, we must delete A first. (B can not be deleted as will be used later.) The problem is how to get the dot (A, C). We are allowed to use extra but limited spaces, for examples, store one or a few intermediate value. Only space constraint.

Thank a lot.

 

[zheng004]

We can store any value as long as using limited space.

My general idea is to store some calculation/calculations between A and B, after replacing B with C, dot (A,C) can be generated from these values. But I can not figure out the details.

 

[jedishrfu]

Okay so this is a homework problem given in computer science?

 

[zheng004]

Okay so this is a homework problem given in computer science?

No, this is not a homework question. Very appreciated if you can help.

 

[jedishrfu]

Okay so who placed this constraint on the problem. What are you trying to do here?

 

[StoneTemplePython]

I am inferring that you are operating over Reals (albeit with floating point arithmetic). I am also assuming that these are LARGE vectors, i.e. not say 2 or 3 entries and not overly sparse, and there isn't some other special structure you've omitted.

Now from here, let's assume each vector has a squared L2 norm = 1. (If this is not the case, you can normalize them and put the actual norms in memo.)

Now run Gram Schmidt on $\mathbf a$ vs $\mathbf b$, and get $\mathbf v$. you now have $\mathbf v = \mathbf b^{ \parallel a}$.

you can do $\mathbf v^T \mathbf c$ and adjust scaling to get $\mathbf a^T \mathbf c$.

side note: there there is a non-parallelizable, but numerically stable, version of Gram Schmidt that you could use.

The open question is what you wanted to use $\mathbf b$ for. Depending on uses, the above may or may not work. If for some reason you need all of it, i.e. $\mathbf b = \mathbf b^{ \parallel a} + \mathbf b^{ \perp a}$, then too bad, I think you're out of luck. If that is the case, it sounds like you're trying to solve for $\mathbf x$ in $\mathbf {Ax} = \mathbf b$, where $\mathbf x$ and $\mathbf b$ are "big" vectors and $\mathbf A$ is a rank one matrix. In this case, the problem is under specified, like your original post.

If you merely need to bound the dot product of $\mathbf a^T \mathbf c$ or whatever, you can do bounds with Cauchy Schwartz. But if you are looking to solve... good luck solving a large n-dimensional equation with a rank one matrix.

 

[zheng004]

I am inferring that you are operating over Reals (albeit with floating point arithmetic). I am also assuming that these are LARGE vectors, i.e. not say 2 or 3 entries and not overly sparse, and there isn't some other special structure you've omitted.

Now from here, let's assume each vector has a squared L2 norm = 1. (If this is not the case, you can normalize them and put the actual norms in memo.)

Now run Gram Schmidt on $\mathbf a$ vs $\mathbf b$, and get $\mathbf v$. you now have $\mathbf v = \mathbf b^{ \parallel a}$}.

you can do $\mathbf v^T \mathbf c$ and adjust scaling to get $\mathbf a^T \mathbf c$.

side note: there there is a non-parallelizable, but numerically stable, version of Gram Schmidt that you could use.

The open question is what you wanted to use $\mathbf b$ for. Depending on uses, the above may or may not work. If for some reason you need all of it, i.e. $\mathbf b = \mathbf b^{ \parallel a} + \mathbf b^{ \perp a}$, then too bad, I think you're out of luck. If that is the case, it sounds like you're trying to solve for $\mathbf x$ in $\mathbf {Ax} = \mathbf b$, where $\mathbf x$ and $\mathbf b$ are "big" vectors and $\mathbf A$ is a rank one matrix. In this case, the problem is under specified, like your original post.

If you merely need to bound the dot product of $\mathbf a^T \mathbf c$ or whatever, you can do bounds with Cauchy Schwartz. But if you are looking to solve... good luck solving a large n-dimensional equation with a rank one matrix.

Thanks for your input. But in order to calculate $\mathbf v^T \mathbf c$, we have to compute and store $\mathbf v$, but the problem is that $\mathbf v$ is a vector and we do not have enough space to store it.

 

[StoneTemplePython]

Thanks for your input. But in order to calculate $\mathbf v^T \mathbf c$, we have to compute and store $\mathbf v$, but the problem is that $\mathbf v$ is a vector and we do not have enough space to store it.

What I suggested is that you overwrite $\mathbf b$ with $\mathbf v$, and store any length difference in a memo.

I should take a step back here. Have you studied linear algebra? Do you understand why you cannot solve for (large) n equations with a rank one matrix?

Barring some kind of omitted special structure, that's what this problem reduces to.

 

[zheng004]

What I suggested is that you overwrite $\mathbf b$ with $\mathbf v$, and store any length difference in a memo.

I should take a step back here. Have you studied linear algebra? Do you understand why you cannot solve for (large) n equations with a rank one matrix?

Barring some kind of omitted special structure, that's what this problem reduces to.

Thanks for your reply. Unfortunately, b can not be overwritten as we need to use later.
I know can we not get a unique solution from Ax = b as you mentioned, so I post the question here. This is problem abstracted from my research, any input is appreciated.

 

[zheng004]

Thanks for your reply. Unfortunately, b can not be overwritten as we need to use later.
I know can we not get a unique solution from Ax = b as you mentioned, so I post the question here. This is problem abstracted from my research, any input is appreciated.

If the vector only has 2 elements, i.e. A = [a1, a2]; B=[b1, b2]; C=[c1, c2], then we can store two values: v1 = (a1+a2-b1-b2) and v2 = (a1+a2+b1+b2). Then we can get dot (A, C) = 1/4 * ( (v2 - (b1+b2-c1-c2))^2 - (v1 + b1 + b2 - c1 - c2)^2). But if vector is lager than 2, I do not know how to figure it out.

 

[jedishrfu]

Closing thread for moderation