diff options
| -rw-r--r-- | results.tex | 5 |
1 files changed, 5 insertions, 0 deletions
diff --git a/results.tex b/results.tex index 2a21586..a9e79e1 100644 --- a/results.tex +++ b/results.tex @@ -51,6 +51,11 @@ It follows that for any vector $x \in \mathbb{R}^n$, $|\frac{1}{N}\|A x\|^2_2 -\ Note that this is clearly not optimal. For example, note that for $k=1$, the solution to the coupon collector problem states that only ${\cal O}(n\log n)$ rows are sufficient before the matrix $A$ has full row rank with high probability, and not ${\cal O}(n^2)$ as stated by Corollary~\ref{cor:number_of_rows_needed}. +\paragraph{Note:} $\Theta(n\log n)$ is in expectation for the coupon collector +problem. If one want an exponentially small probability of failure, then +I think results on the coupon collector problem also imply that a quadratic +number of rows are required. + \subsection{More Direct Approach} Here we work on $\mathbb{F}_2$. An $n\times n$ binary matrix can be seen as |