HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Attempt to reduce to problem of inner product

Submitted by: @import:stackexchange-cs··
0
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.

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.

Context

StackExchange Computer Science Q#148270, answer score: 5

Revisions (0)

No revisions yet.