Reshaping data vector into a matrix for deconvolution using a circulant matrix

Question

Suppose we have a circulant matrix S made from pseudorandom binary sequence of length $N$ consisting of $0$'s or/and $1$'s. $1$ means that we can inject something for chemical analysis and $0$ means we do not inject into an analyzer.

The duration $D$ of this sequence is $N \times\Delta t$. A single chemical analysis, after one injection, will last at least $D$ seconds and this is how the sequence is designed. However, after running plenty of injections, we will have waited for a much longer time than $D$ so that each analysis is completed.

I have a question regarding the right approach of matrix multiplication to deconvolve the signal from the instrument according to the pseudo-random binary sequence. The detector has its own data sampling rate $f_s$. The circulant matrix $S$ will have dimensions of $L \times L$. However the raw data vector from the instrument will be extensively longer due to data sampling rate. Say, if our data sampling rate is $20 \texttt{Hz}$, and $\Delta t$ was $2$s, and $L=127$, then the number of points in the vector prepared for deconvolution would be $127\times 20\times 2$. This makes the data vector, $v$, $5080$ elements long.

The simple deconvolution equation would be $$\text {Recovered signal} = S^{-1} v$$

What is the logical way to make the matrix multiplication compatible, by reshaping either $S$ or $v$ with $V$ to allow deconvolution? Downsampling $v$ to $127$ data points will cause a significant loss of data, although it is done by some researchers in older papers.

Alternatively, some convert the vector $v$ into a 127 row matrix, $M$ so that multiplication becomes compatible, and place the remaining data in the columns of $M$.

What is the mathematical basis of doing so?

Answer 1

By having a matrix with a circulant structure where all row pairs, at all relative shifts are nearly orthogonal, you can decorrelate:

PRBS (Pseudo Random Binary Sequence) almost certainly refers to a so-called [maximal length sequence][1] or $m-$sequence which is generated by a primitive recurrence of order $n$ giving maximal period $2^n-1.$ If you write the sequence in the $\pm 1$ formulation and border on the left and top by all 1 columns you obtain a Hadamard matrix.

How does this matrix help in decorrelation? The $m-$sequence is given by $$ s_t=(-1)^{a_t},\quad 0\leq t\leq 2^n-2, $$ where $a_n=\mathrm{tr}(\alpha^t)$ with $\mathrm{tr}:GF(2^n)\rightarrow GF(2)$ the trace mapping. Since the trace map is balanced with equal number of zero and one outputs, but $\{\alpha^t:0\leq t\leq2^n-2\}=GF(2^n)^\ast$ i.e., the nonzero elements of the field, we have $$ \sum_{t=0}^{2^n-2} s_t = \sum_{t=0}^{2^n-2} (-1)^{a_t} =-1 \quad(1). $$ Note that two different shifts $(s_t)$ and $(s_{t+\tau})$ [sum over indices modulo $2^n-1$ to get cyclic correlation] of the sequence also have correlation $-1,$ since the correlation is $$ \sum_{t=0}^{2^n-2} s_t s_{t+\tau}= \sum_{t=0}^{2^n-2} (-1)^{\mathrm{tr}(\alpha^t(1+\alpha^\tau))}=-1$$ and when $\tau \neq 0 \pmod{2^n-1},$ the above correlation is just a shift of the sum (1) and thus the same

This is the correlation of any two rows the unbordered circulant part of the matrix. I haven't checked the code but if this is the part they are using then the correlation has magnitude 1 compared to the peak of $2^n-1.$

If they are using the full matrix [since they want a Hadamard transform] then the correlation of any two rows (other than the first) of the bordered matrix will be in general at most off by 4 from this value so in the interval $$ \{-5,-3,-1,1,3\} $$ while the correlation of the first row with any other row will be zero. [1]: https://en.wikipedia.org/wiki/Maximum_length_sequence

Answer 2

To circumvent the size difference between $S$ and $v$, one can use JPL codes. These are a XOR (which is modulo $2$ addition) of two or more maximal length sequences of coprime sizes.

After 2nd thought this is not the same as I advised in my comments. For two bit sequences of coprime sizes $2^n - 1$ and $2^m - 1$, make the size the period of each sequence as periodic infinite bit sequence. Adding them with XOR gives a new infinite bit sequence with the product of both periods as period (since they are coprime). Take one period of this sequence as the resulting PRBS $x$. This can be used as circulant matrix $K$, but on a permuted $v$: $v_i$ must then be the output of the ($i$ mod $2^n - 1$)th sampler on timeframe $i$ mod $2^m - 1$.

You can either reorder $v$ for JPL codes, or use instead the approach from my comments and find the matrix $M=(S_{ij} + T_{kl})_{nm}$ (mod 2) with $i=n, j=m, k=n, l=m$ modulo the other sequence length. It might be that it depends on the context which one is better. The autocorrelation of $K$ is the same as that of $M$ since it's merely permuted. Edit: no that does not follow. But the autocorrelation of the samplers is that of the maximal length sequence, and the autocorrelation over the timeframes the other sequence.

I'm not sure what to do if you can't exactly control the amount of timeframes, but I think it's fine to add zeroes at the end of $v$ to get the right dimension.