Timeline for On Sampling rank $r$ matrices
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 12, 2019 at 21:38 | vote | accept | Turbo | ||
| Dec 12, 2015 at 23:45 | answer | added | Tony Huynh | timeline score: 4 | |
| Dec 12, 2015 at 20:04 | comment | added | Turbo | @ViditNanda that is correct interpretation (a parametrization would solve deterministically but may be some other cleverer way as well (which should technically be called paremeterization as well if it works deterministically)) | |
| Dec 12, 2015 at 19:34 | comment | added | Vidit Nanda | @kodlu I think it is pretty clear what is being asked. Q1: given $n^2$ integer of absolute value smaller than $d$, what are the odds that the matrix they generate has rank $r$? And Q2, what is an efficient algorithm for uniformly sampling from the set of $n \times n$ matrices with entries < $d$ and rank $r$? Deterministic only means that the algorithm should not be probabilistic in the sense of giving the right answer only with probability $> 1 - \epsilon$ for a priori choice of $\epsilon$. | |
| Dec 12, 2015 at 19:25 | history | edited | Turbo | CC BY-SA 3.0 |
added 1 character in body
|
| Dec 12, 2015 at 19:24 | comment | added | Turbo | no oh boy I will make it clearer | |
| Dec 12, 2015 at 16:34 | review | Close votes | |||
| Dec 13, 2015 at 12:50 | |||||
| Dec 12, 2015 at 14:05 | comment | added | kodlu | I think he means choose $a_{1,1},a_{1,2},\ldots,a_{n,n}$ uniformly from {$-d,\ldots,-1$}$\cup${$1,\ldots,d$} but then he talks about deterministic sampling in the comments, which is puzzling. | |
| Dec 12, 2015 at 11:59 | comment | added | Federico Poloni | $[-d,d]\not\subseteq[0,0]$ does not look like well-formed notation either, to me, and I still don't understand what you mean by it. | |
| Dec 12, 2015 at 8:34 | history | edited | Turbo | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Dec 12, 2015 at 8:34 | comment | added | Turbo | @FedericoPoloni I tried to eradicate BloodPuddings degenerate condition | |
| Dec 12, 2015 at 7:29 | comment | added | Federico Poloni | What do you mean by "sample $n^2$ integers in $0\subsetneq[-d,d]$"? Is there a typo in your notation? It doesn't seem well-formed even syntactically, because $0$ is not a subset. | |
| Dec 11, 2015 at 9:08 | comment | added | Set | that I don't know | |
| Dec 11, 2015 at 9:07 | comment | added | Turbo | @BloodPudding that should help in probability calculation though right? | |
| Dec 11, 2015 at 9:06 | history | edited | Turbo | CC BY-SA 3.0 |
added 22 characters in body
|
| Dec 11, 2015 at 9:06 | comment | added | Turbo | @BloodPudding that is true but that does not help getting away to sample deterministically. | |
| Dec 11, 2015 at 9:04 | comment | added | Set | The parametrization is the Grassmanian | |
| Dec 11, 2015 at 9:00 | history | edited | Turbo | CC BY-SA 3.0 |
added 11 characters in body
|
| Dec 11, 2015 at 8:59 | comment | added | Set | I'm assuming this is for $d\neq 0$. | |
| Dec 11, 2015 at 8:57 | history | asked | Turbo | CC BY-SA 3.0 |