# Dot Product of Streaming vectors

Tags:
1. Jun 25, 2017

### 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!!!

2. Jun 25, 2017

### Buffu

Store A in B and then dot B and C.

3. Jun 25, 2017

### zheng004

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.

4. Jun 25, 2017

### Buffu

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 ?

5. Jun 25, 2017

### zheng004

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.

6. Jun 25, 2017

### Buffu

So you can store 2 floats at max ?

7. Jun 25, 2017

### Staff: Mentor

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

8. Jun 25, 2017

### zheng004

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

9. Jun 25, 2017

### zheng004

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.

10. Jun 25, 2017

### zheng004

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.

11. Jun 25, 2017

### Staff: Mentor

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

12. Jun 25, 2017

### zheng004

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

13. Jun 25, 2017

### Staff: Mentor

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

14. Jun 25, 2017

### 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.

Last edited: Jun 25, 2017
15. Jun 25, 2017

### zheng004

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.

16. Jun 25, 2017

### StoneTemplePython

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.

17. Jun 25, 2017

### 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.

18. Jun 25, 2017

### zheng004

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.

19. Jun 26, 2017