I have $n$ random vectors ${\bf r}_i$ for $i=1,2,\dots,n$, each with dimension $1 \times m$, and $n$ random matrices ${\bf S}_i$ for $i=1,2,\dots,n$, each with dimension $M \times m$. The elements of ${\bf r}_i$ and ${\bf S}_i$ belong to GF(2). ${\bf r}_i$'s are i.i.d and Every ${\bf r}_i$ has only one non-zero element and the probability that its $k$-th element is 1 is $p_k$ for a non-increasing probability distribution $p_k$ such that $\sum_{k=1}^m p_k =1$. ${\bf S}_i$'s are i.i.d random matices and the $jk$-th element of ${\bf S}_i$ is chosen to be equal to 1 independently of other elements according to a Bernoulli random distribution with probability $p_k$ (this is equal to the distribution discussed above). For vectors ${\bf a}_i$ of size $1 \times M$ for $i=1,2,\dots,n$ whose elements belong to GF(2) we define the $n \times m$ random matrix $\mathbb{H}_{n \times m}$ as \begin{equation} \mathbb{H}_{n \times m}({\bf a}_1, {\bf a}_2, \dots, {\bf a}_n) = \begin{bmatrix} {\bf r}_1 + {\bf a}_1 {\bf S}_1 \\ {\bf r}_2 + {\bf a}_2 {\bf S}_2 \\ \vdots \\{\bf r}_n + {\bf a}_n {\bf S}_n \end{bmatrix} \end{equation} I need to find the expected value of the minimum rank of matrices $\mathbb{H}_{n \times m}$ when the expectation is taken over all such random matrices ${\bf S}_i$ and random vectors ${\bf r}_i$ and the minimum rank is found over all such vectors ${\bf a}_i$. In other words I need to find \begin{equation} \mathbb{E}_{{\bf r}_1 \dots {\bf r}_n {\bf S}_1 \dots {\bf S}_n} \left[ \min_{{\bf a}_1 \dots {\bf a}_n} \left[\mathrm{rank}\left( \mathbb{H}_{n \times m}({\bf a}_1, {\bf a}_2, \dots, {\bf a}_n) \right) \right] \right] \end{equation} I know that this is very complicated to find. However, If I can find any bounds that would also be nice. Can I approximate the nasty rank function with a better well-behaving convex function? I know that this is possible in case of square matrices but $\mathbb{H}$ is an $n \times m$ matrix. If it helps, we can assume that $m >> M$ and $m >> n$ and we may assume that the above probability distribution is Zipfian. Any thoughts would be highly appreciated.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.