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

Question

Shlomo Geva 2018-1-31

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/379929-how-to-generate-a-set-of-n-mutually-orthogonal-n-being-a-power-of-2-n-dimensional-binary-vectors

评论： Matt J 2023-4-30

采纳的回答： Matt J

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,...)?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Matt J 2021-3-8

2
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/379929-how-to-generate-a-set-of-n-mutually-orthogonal-n-being-a-power-of-2-n-dimensional-binary-vectors#answer_641686

编辑：Matt J 2021-3-8

在 MATLAB Online 中打开

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

3 个评论
显示 1更早的评论隐藏 1更早的评论

Mohamed 2023-4-30

移动：Matt J 2023-4-30

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 2023-4-30

在 MATLAB Online 中打开

@Mohamed

This line was used above to verify mutual orthogonality:

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

请先登录，再进行评论。

Answer 2

Steven Lord 2021-3-8

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/379929-how-to-generate-a-set-of-n-mutually-orthogonal-n-being-a-power-of-2-n-dimensional-binary-vectors#answer_641931

See the hadamard function.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Matt J 2021-3-8

在 MATLAB Online 中打开

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 2018-1-31

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/379929-how-to-generate-a-set-of-n-mutually-orthogonal-n-being-a-power-of-2-n-dimensional-binary-vectors#answer_302659

在 MATLAB Online 中打开

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

9 个评论
显示 7更早的评论隐藏 7更早的评论

Matt J 2021-3-8

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

Shlomo Geva 2021-3-8

Yep. Thanks Matt!!

Shlomo Geva 2021-3-8

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.

请先登录，再进行评论。