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.