2
$\begingroup$

Question: For $N$ be a power of $2$, let $A$ be a random $d \times d$ submatrix of the $N \times N$ Hadamard matrix (the matrix of the Hadamard/Walsh-Fourier transform). What is the best known upper bound on the probability that $A$ is singular? The range of $d$ I'm asking about is, say, $\log N \leq d \leq N^{0.001}$.

Other stuff: One might hope that there is a universal constant $c < 1$ such that the probability is at most $c^d$. I'm not even close to this: at the risk of asking a trivial question, is it known or straightforward to show that the probability goes to $0$ as $N$ (and thus $d$) approach $\infty$?

A couple things that I am aware of:

  • If $d$ is "small" (certainly at most $\frac12\log N$; maybe a more stringent bound is required), then this paper of Frankl, Rödl, and Wilson says that the distribution of $A$ is very close to that of a random matrix with i.i.d. uniform $\pm 1$ entries.

  • For non-square random submatrices, this book chapter by Vershynin has a few results. This case is pretty interesting in compressed sensing and well-studied in terms of restricted isometry properties. However, I have been unable to find anything that applies to the case of square random submatrices.

$\endgroup$
2
  • $\begingroup$ When N > 20 one likely has many choices for the matrix, which distribution and structure are largely unknown. Are you making any assumptions on N or on the distribution of the Hadamard matrices of that order? $\endgroup$ Mar 29, 2014 at 22:02
  • $\begingroup$ I followed the link, so it become clear you want N a power of 2. For clarity, you might edit the post to make that explicit. Also, the more general form is of interest. ( I see that it is explicit. Thank you.) $\endgroup$ Mar 29, 2014 at 22:56

0

Your Answer

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

Browse other questions tagged or ask your own question.