7
$\begingroup$

I want to construct a sparse random binary matrix ${{\bf{H}}_{m \times n}}$ that has the following properties

1- Faction of columns of weight $i$ is ${v_i}$ .

2- Fraction of rows of weight $i$ is ${h_i}$.

3- No two columns in the matrix have an overlap greater than one.

For instance, for ${v_2} = 7/10,{v_3} = 3/10$ and ${h_4} = 2/5,{h_5} = 3/5$ the random binary matrix can be represented as

${{\bf{H}}_{5 \times 10}} = \left[ {\begin{array}{*{20}{c}} 1&1&0&1&1&0&0&1&0&0\\ 0&1&1&0&1&1&1&0&0&0\\ 0&0&0&1&0&0&0&1&1&1\\ 1&1&0&0&0&1&1&0&1&0\\ 0&0&1&0&0&1&0&1&0&1 \end{array}} \right]$

The matrix ${\bf{H}}$ is called irregular low density parity check matrix in channel coding. There are a few algorithms that have been proposed to construct the matrix for low to moderate dimension (maximum n=10e4,m=n/2) such as progressive edge growth (PEG). How can I construct ${\bf{H}}$ for given ${v_i}$ and ${h_i}$ and the constraint 3 randomly for large dimension ( for example n=10e5,m=n/2)?

Improve this question
$\endgroup$
4
  • $\begingroup$ I think your matrix has $h_3 = 1$ at the moment. $\endgroup$
    – Steve Huntsman
    Sep 24, 2015 at 20:30
  • $\begingroup$ Do you need the fractions to come out exactly right or will an approximation suffice? Similarly, do you need to sample exactly uniformly from the space of all possibilities or will approximately uniformly suffice? $\endgroup$
    – Timothy Chow
    Sep 25, 2015 at 15:11
  • $\begingroup$ Thank you. It doesn't need to satisfy the fractions exactly. In other words, we should be able to find large enough m and n to satisfy the fractions for a desired small error. The samples can be approximately uniformly random. $\endgroup$
    – user51780
    Sep 25, 2015 at 17:52
  • $\begingroup$ how "dense" are your constraints. What do you typically expect the following ratios to be? $$\frac{\mathrm{Number~~ of~~ v_i\neq 0}}{n}$$ and $$\frac{\mathrm{Number~~ of~~ h_i\neq 0}}{m}$$ $\endgroup$
    – kodlu
    Nov 26, 2015 at 3:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.