Timeline for How to sample uniformly from singular matrices
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Feb 6, 2014 at 17:13 | comment | added | Bill Bradley | @marshall By the way, what was your original reason for wanting to sample from these matrices? | |
| Jan 30, 2014 at 20:52 | answer | added | Bill Bradley | timeline score: 1 | |
| Jan 30, 2014 at 15:16 | answer | added | Bill Bradley | timeline score: 3 | |
| Jan 24, 2014 at 6:18 | comment | added | ofer zeitouni | @marshall You did not misunderstand, you are right. ( I think that checking singularity can be done in slightly less than n^3 but am not sure.) | |
| Jan 24, 2014 at 6:17 | comment | added | ofer zeitouni | @Bill Bradley: you are right, I did not note that (I was acting from memory and did not remember that). I'll erase my earlier comment. | |
| Jan 24, 2014 at 2:38 | comment | added | Bill Bradley | @oferzeitouni Are you sure that Bourgain et al's results don't apply to the {0,1} case? I don't want to give the impression that I understand their results deeply, but Corollary 3.3 appears to be specifically designed for arbitrary (i.e. non-symmetric) distributions. | |
| Jan 23, 2014 at 22:41 | comment | added | marshall | @oferzeitouni I was thinking it would take $2^n/n^2$ matrices on average to get a single singular matrix and each one would take $n^3$ time to check. Did I misunderstand? | |
| Jan 23, 2014 at 19:58 | comment | added | ofer zeitouni | @marshall not that it matters much, but the lower bound is actually of order $n^2 2^{-n}$, so you can shave a polynomial from the simulation time :) | |
| Jan 23, 2014 at 19:01 | comment | added | marshall | @oferzeitouni / Bill Bradley. Thanks for the comments. I suppose however that even this pessimism doesn't preclude something better than $2^n n$ time per matrix sample (the expected time to find a singular matrix times the time to check if a matrix is singular), which seems to be what a naive method would give you. Maybe there is an MCMC style approach... | |
| Jan 23, 2014 at 2:41 | comment | added | Bill Bradley | For the record, the Bourgain-Vu-Wood paper gives $(1/\sqrt{2} + o(1))^n$ as an upper bound for the probability that a matrix is singular, versus the $2^{-n}$ lower bound mentioned above by Zeitouni. Note that the abstract of Bourgain et al refers to $\pm 1$ Bernoulli matrices, but their Corollary 3.3 seems to include the $0/1$ Bernoulli matrices under discussion here. | |
| Jan 22, 2014 at 16:47 | comment | added | ofer zeitouni | I do not have an answer but have the following comment that maybe indicates why the problem is hard: it is widely believed that a ``typical'' singular Bernoulli matrix should have two co-linear rows (an event which occurs roughly with probability $2^{-n}$ in exponential scale). The best estimate for the singularity probability is however larger (larger exponent) - for +/-1 entries, record is held by Bourgain-Vu-Wood as far as I know. Now, if you had such an algorithm as you are after, you could maybe check whether the belief is true... | |
| Jan 20, 2014 at 17:34 | review | First posts | |||
| Jan 20, 2014 at 17:55 | |||||
| Jan 20, 2014 at 17:17 | history | asked | marshall | CC BY-SA 3.0 |