Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$).

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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

share|improve this answer
    
Thanks! I will look into the references. –  adas Dec 5 '13 at 15:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.