How to generate a set of N mutually orthogonal (N being a power of 2) N-dimensional binary vectors [+1,-1]?

For instance:

with N=2 we could have [1 1; 1 -1]

with N=4, we could have [1 1 1 1; 1 1 -1 -1; 1 -1 1 -1; 1 -1 -1 1]

How to efficiently generate N mutually orthogonal binary vectors for larger N (8,16,32,64,...,4096,...)?

Answer 1

[Matt J]

N=4096;

[C,C0]=deal([1 1;1 -1]);

tic;
for i=1:log2(N/2)
   C=kron(C0,C);
end
toc

Elapsed time is 0.079038 seconds.

isOrthogonal=isequal(C*C.', N*speye(N))

isOrthogonal = logical
   1

C

C = 4096×4096

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 1 -1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1

[Shlomo Geva]

Nice Matt. Thank you.

[Mohamed]

Each signal must be orthogonal to every other 15 signals in the set. What function do i use since (dot) is for two variables?

[Matt J]

@Mohamed

This line was used above to verify mutual orthogonality:

isOrthogonal=isequal(C*C.', N*speye(N))

Answer 2

[Steven Lord]

See the hadamard function.

[Matt J]

For some reason, I find this a fair bit slower than the kron-based solution

N=4096;

tic;
[C,C0]=deal([1 1;1 -1]);
for i=1:log2(N/2)   
   C=kron(C0,C);
end
toc

Elapsed time is 0.075004 seconds.

tic; hadamard(N); toc

Elapsed time is 0.305544 seconds.

Answer 3

[Walter Roberson]

(dec2bin(0:(2^(N-1)-1),N)-'0') * 2 - 1

[Shlomo Geva]

Thanks for the speedy answer. OOPS my bad. I just noticed that while editing my question I managed to delete the most important constraint - the set of N vectors sought must be mutually orthogonal. It is a binary [+1,-1] basis set of N vectors for the N-Dimensional set of [+1,-1] binary vectors of dimensionality N. Therefore, only N vectors can satisfy this constraint (although multiple sets of N vectors may exist). Furthermore, N can be quite large (e.g. N=4096) and so a solution must be feasible and cannot rely on anything exhaustive (i.e. brute-force)

[Shlomo Geva]

For instance, look at all possible 4 dimensional {+1/-1} vectors:

>> N=4; (dec2bin(0:(2^N-1),N)-'0') * 2 - 1

ans =

-1 -1 -1 -1

-1 -1 -1 1

-1 -1 1 -1

-1 -1 1 1

-1 1 -1 -1

-1 1 -1 1

-1 1 1 -1

-1 1 1 1

1 -1 -1 -1

1 -1 -1 1

1 -1 1 -1

1 -1 1 1

1 1 -1 -1

1 1 -1 1

1 1 1 -1

1 1 1 1

There can only be 4 mutually orthogonal vectors in 4 dimensional space.

We could, for instance, choose the following set (or its binary complement):

-1 -1 -1 -1

-1 -1 1 1

-1 1 -1 1

1 -1 -1 1

Or we could choose this set (or its binary complement):

-1 -1 -1 1

-1 -1 1 -1

-1 1 -1 -1

-1 1 1 1

[Walter Roberson]

You just came back to this after more than 2 years. Are you still looking for a solution?

[Matt J]

Shlomo Geva replied:

3 years actually :-)

Yes, I am still interested in a simple solution - if exists. Not sure.

Brute force is possible of course, but I am very curious to know whether there is some simple rule that helps select rows, or an efficient procedure.

For instance, in 4D, the first solution above corresponds to the rows [1 4 6 7] of all possible 16 rows, while the second solution corresponds to rows [2 3 5 8].

Actually, a more general problem is also of interest - generating an N dimensional set of orthonormal Real vectors. We currently perform SVD on a random matrix of dimensionality NxN to get an orthonormal basis set. e.g. [~,~,v,'econ']=svd(randn(N,N)); Perhaps not the most efficient, but a one liner in Matlab is pretty good otherwise. However, this can only go so far. At dimensionality of 32K it takes half an hour on a decently powered typical SOTA top-end desktop (96 cores) with ample memory (1.5 TB), but we stop there.

(If there is no available solution, it will make for a nice CODY problem, with a basic brute force baseline solution.)

[Matt J]

Actually, a more general problem is also of interest - generating an N dimensional set of orthonormal Real vectors.

Simple:

V=speye(N);

[Shlomo Geva]

Thanks. Indeed eye(N) is a trivial solution. But I omitted to indicate something - I want the orthonormal basis set to be arbitrarily oriented. This essentially means that none of the elements of the NxN matrix are likely to be zero. A sparse matrix cannot be used. Furthermore, I want to generate such a matrix on demand so that multiple montecarlo simulations can be executed with differently oriented such matrices.

In principle you may start with one random vector, then choose another vector orthogonal to it, then choose another that is orthogonal to the first two, and so on. This quickly becomes very expensive.

[Matt J]

As a simple extension of my other answer, you could do this,

[Q1,~]=qr(rand(2^8));
[Q2,~]=qr(rand(2^7));

V=kron(Q1,Q2);

[Shlomo Geva]

Yep. Thanks Matt!!

[Shlomo Geva]

On the machine I use we can go up to 131072 x 131072 x 8 bytes (using 2^9 and 2^8 in code above). It takes 10 seconds. We have 1.5TB of RAM. After that we are toast, but that is all we need so this is great.