patternMinor
Attempt to reduce to problem of inner product
Viewed 0 times
problemproductattemptreduceinner
Problem
The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$?
The problem of max product: likewise two sets each $n$ vectors (I forgot to mention in both cases values are binary). We want to find maximal inner product (one vector from set $A$ and one from $B$).
I want to find a reduction between OV to max. Inner product.
My idea:
Use negative values, claim its equivalent with negative value and possitive values.
What I mean, OV reduced to max. Inner prod with negative values by multiplying all by $-1$.
Then if maximum is zero... Orthogonality. Else, no orthogonality.
But i need to argue negative max inner product equivalent to max. Inner product.
Maybe there is another way?
If it does not work, also interested in reduction from sat.
The problem of max product: likewise two sets each $n$ vectors (I forgot to mention in both cases values are binary). We want to find maximal inner product (one vector from set $A$ and one from $B$).
I want to find a reduction between OV to max. Inner product.
My idea:
Use negative values, claim its equivalent with negative value and possitive values.
What I mean, OV reduced to max. Inner prod with negative values by multiplying all by $-1$.
Then if maximum is zero... Orthogonality. Else, no orthogonality.
But i need to argue negative max inner product equivalent to max. Inner product.
Maybe there is another way?
If it does not work, also interested in reduction from sat.
Solution
One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}_{ij} = x_i x_j$ (the vectors have length $k^2)$.
We have
$$
\langle \hat{x}, \hat{y} \rangle =
\sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2.
$$
Therefore if you know the minimum inner product, you can solve OV. It remains to negate all vectors in one of the sets.
We have
$$
\langle \hat{x}, \hat{y} \rangle =
\sum_{ij} x_i x_j y_i y_j = \langle x,y \rangle^2.
$$
Therefore if you know the minimum inner product, you can solve OV. It remains to negate all vectors in one of the sets.
Context
StackExchange Computer Science Q#148270, answer score: 5
Revisions (0)
No revisions yet.