# Designing almost orthogonal vectors in a deterministic manner

Consider the vector space $\mathbb{R}^n$, the standard inner product $\langle \cdot,\cdot \rangle:\mathbb{R}^n\times\mathbb{R}^n\rightarrow \mathbb{R}$, and some $0<\epsilon\leq \frac{1}{\sqrt{n}}$. Is it possible to generate a set of $M$ vectors, say $\mathcal{S}$, in a deterministic fashion (not random), such that the vectors in $\mathcal{S}$ satisfy the following properties:

• all the entries of the vectors come from $\{\frac{-1}{\sqrt{n}},\frac{1}{\sqrt{n}}\}$, so that $||\mathbb{x}||_2=1\,\,\forall \mathbb{x}\in\mathcal{S}$,

• $\mathbb{x},\mathbb{y}\in\mathcal{S}\Rightarrow|\langle \mathbb{x},\mathbb{y} \rangle| <\epsilon$, i.e., the vectors in $\mathcal{S}$ are almost orthogonal to each other.

Kindly note that a similar question was asked before (Almost orthogonal vectors in subsets of euclidean space), but it asked for an upper bound on $M$ for given $n,\epsilon$ - the answer was $M\leq \frac{n(1-\epsilon^2)}{1-n\epsilon^2}$. I am interested in knowing if there is a deterministic way of constructing $\mathcal{S}$ of reasonable size.

Let me also explain an approach that I thought of (but got stuck) - consider $\mathcal{C}=[n, k, d]_{2}$, a binary linear code with $\frac{n}{2}(1-\epsilon)\leq d <\frac{n}{2}(1+\epsilon)$, and map its codewords (of length $n$) to real-valued sequences in $\{\frac{-1}{\sqrt{n}},\frac{1}{\sqrt{n}}\}^n$ such that $0$ maps to $\frac{-1}{\sqrt{n}}$ and $1$ maps to $\frac{1}{\sqrt{n}}$. Then consider the set of real-valued sequences, say $\mathcal{T}$, corresponding to the subset of codewords in $\mathcal{C}$ whose Hamming weight is at least $d$ and at most $\frac{n}{2}(1+\epsilon)$. Then one can show that $\mathcal{T}$ is a candidate for $\mathcal{S}$; however I have not been able to design a linear code for which tight upper and lower bounds on $|\mathcal{T}|$ can be obtained (i.e., I don't have bounds/expression for $M$ in terms of $n,\epsilon$).

-

In [1] a collection of $M$ binary vectors over $\{\pm 1\}^n$ is constructed such that:

$n=2^m-1$, $M=n(n+2) \approx n^2$ and their unnormalized inner products satisfy

$|<v_i,v_j>|\leq 1+\sqrt{2(n+1)}$

whenever $i\neq j$ by taking the finite field $GF(2^m),$ letting $a$ be a primitive element in $GF(2^m)$ and defining the collection of vectors

$((-1)^{tr(a^t)})_{t=0}^{2^m-1}$, $((-1)^{tr(a^{dt})})_{t=0}^{2^m-1}$ and

$((-1)^{tr(a^{t+s}+a^{dt})})_{t=0}^{2^m-1}$, for $s=0,1,\ldots,2^m-2.$

and all their cyclic shifts as $\{v_i\}$ , provided $\gcd(d,2^n-1)=1$. Normalizing, as you require, by letting $x_i=v_i/\sqrt{n}$ yields

$|<x_i,x_j>|\leq (1+\sqrt{2(n+1)})/n={\cal O}(n^{-1/2})$ Since the construction exists for all $n_m=2^m-1,$ $m\geq 2$ you can achieve any $\epsilon>0$ for $n$ large enough.

There has been more constructions since 1992, and the best ones have $M\approx n^{1+k}$ sequences ($n^k$ sequences and their cyclic shifts), and $|<x_i,x_j>|\leq 1+ k \sqrt{n+1}$.

Intriguingly, over $C^n$, it is possible to construct a family with the same parameters as in [1], by using Galois Rings instead of Galois fields, and alphabet $\{\pm 1, \pm i\}$ where $i^2=-1$ but where the bound is now

$|<v_i,v_j>|\leq 1+\sqrt{(n+1)}$

and that $\sqrt{2}$ magnitude difference is in practice very useful for CDMA communication systems since it reduces interference in wireless communications [2].

1. Gold, R. (October 1967). "Optimal binary sequences for spread spectrum multiplexing (Corresp.)". IEEE Transactions on Information Theory 13 (4): 619–621.

2. Boztas, S., Hammons, A.R., Kumar, P.V., "4-phase sequences with near-optimum correlation properties", Information Theory, IEEE Transactions on Information Theory 38 (3):1101-1113, 1992.

-
You appear to have two different accounts (this one and this one). In order to merge them, please follow the instructions here: mathoverflow.net/help/merging-accounts – Ricardo Andrade Dec 6 '13 at 1:53

I think that if you relax the normalized $|| x ||_2=1,$ requirement, you may be able to get something very close to this with various research in the dimension reductiona area. Because for M < N (which I think is the only case of interest), your collection of M vectors of length N forms a projection matrix.

I'm a bit rusty in the topic myself, but many good papers can be found on Jelani Nelson's page here

-
Thanks! I will look into the references. – adas Dec 5 '13 at 15:58