Observation : A shifted transversal design (STD) is similar to the adjacency matrix of an (unbalanced) expander graph.

STD(n;q;k) is a matrix construction algorithm that accepts parameters : n,q and k to produce a (qk x n) 0-1 matrix with certain special properties. Each of the n columns has k 1’s in it, which are distributed, one in every q x n block. Each row has usually \lceil \frac{n}{q} \rceil 1’s in it. Such matrices are very useful as pooling design schemes and error-correcting codes, among other things. The STD algorithm is due to N. Thierry-Mieg.

Expander Graphs are sparse but highly connected graphs. From here, we learn that a bipartite graph H = (X,Y,E) is said to be an (n,m,d, \alpha, \gamma)-expander if |X|=n, |Y|=m, the degree of each node in X is d, and for every A \subseteq X, \left|A\right| \le \alpha n, the set of vertices N(A) \subseteq Y that are adjacent to A satisfies \left|N(A)\right| \ge \gamma \left|A\right|. A higher value of \gamma implies a better expansion property.

The connection between STD’s and EG’s stems from the fact that STD(n;q;k) creates n distinct (actually disjunct) columns of length qk with column weight k and this is similar to the adjacency matrix of an unbalanced expander with left degree k and |X|=n and |Y|=qk.

To construct such a matrix, via STD, we do as follows :

Given the parameters n, q and k, the binary matrix STD(n;q;k) can be constructed as follows. The STD has a layered construction consisting of k layers of q x n binary matrices. For all j \in \{0, \ldots,k-1\}, let M_{j} be a q \times n boolean matrix representing layer L(j), with columns C_{j,0}, \ldots, C_{j,n-1}. Let the circular shift operator, \sigma_{q}, be defined as, \forall (x_{1},\ldots,x_{q}) \in {0,1}^{q}, \quad \sigma_{q} \left[ \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{q} \end{array} \right] = \left[ \begin{array}{c} x_{q} \\ x_{1} \\ \vdots \\ x_{q-1} \end{array} \right] and C_{0,0}= \left[ \begin{array}{c} 1 \\ 0 \\ \vdots \\ 0 \end{array} \right]. Note that \sigma_{q} is a cyclic function and when applied q times maps \{0,1\}^{q} onto itself, \quad \sigma_{q}^{s} \left[ \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{q} \end{array} \right] = \left[ \begin{array}{c} x_{1} \\ x_{2} \\ \vdots \\ x_{q} \end{array} \right], s=q. To design a layer L(j), for all i \in \{0, \ldots,n-1\} construct C_{j,i}=\sigma_{q}^{s(i,j)} C_{0,0}, where,

  • if j<q : s(i,j)=\displaystyle\sum_{c=0}^{\Gamma}j^{c} \Big\lfloor \frac{i}{q^{c}} \Big\rfloor
  • if j=q : s(i,q)=\lfloor \frac{i}{q^{\Gamma}} \rfloor where \Gamma = \lceil \frac{\log n}{\log q} \rceil -1

    • The layers L(j) are put together to form M by, \mathsf{STD}(n;q;k)= \displaystyle\bigcup_{j=0}^{k-1} L(j).

    Note : q is a prime number. To get the required m rows with column weight k, try to find the smallest prime, q \ge \frac{m}{k} and q \ge k-1.

    In fact, any constant column-weight d-disjunct matrix has such a property. This property of d-disjunctness seems to be related to linear time decoding capabilities of codes. Not surprisingly, the STD is similar in nature to low density parity check (LDPC) codes.

    The point of all this being that, STD has a very fast and clean construction method which could come in handy while creating expander graph-type structures (and codes with error-correcting properties). This is especially useful for the compressed sensing methods that use sparse matrices and the MATLAB codes that go with it.

    % A STD-based method to create the sparse measurement matrix (used for compressed sensing)

    % Here k is the number of ones per column
    % qk is the number of rows
    % So if m rows are needed, choose q : prime >= m/k and k<=q+1
    % n is the number of columns

    function M=std(n,q,k)

    if rem(log(n),log(q)) == 0
    Gamma=log(n)/log(q)-1;
    else
    Gamma=floor(log(n)/log(q));
    end

    flag=0;
    % Check if STD Correction is needed
    if k == q+1 && floor((n-1)/q^Gamma) < q-1
    flag=1;
    end

    format short
    M=zeros(k*q,n);
    s=zeros(k,n);

    C00=zeros(q,1);
    C00(1)=1;

    for j=1:k
    for i=1:n
    if j-1 < q
    for c=0:Gamma
    s(j,i)=s(j,i)+ ((j-1)^c)*floor((i-1)/q^c);
    end
    elseif j-1==q
    s(j,i)=floor((i-1)/q^Gamma);
    end

    M((j-1)*q+1:j*q,i)=circshift(C00,s(j,i));
    end
    end

    if flag==1
    M((k-1)*q+(floor(n/q^Gamma)+1)+1:k*q,:)=[];
    end

    %End of Function