most recent 30 from http://mathoverflow.net 2013-06-19T20:58:32Z http://mathoverflow.net/feeds/question/87711 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/87711/derandomizing-random-matrices Michal Kotowski 2012-02-06T19:48:56Z 2012-02-08T20:30:35Z

<p>My question is rather general - what is known about derandomization of results in random matrix theory, high-dimensional geometry, Banach spaces etc. using probabilistic constructions (like estimates of eigenvalues, Dvoretzky's theorem, metric embeddings)? Here I'm interested both in fully explicit counterparts of random constructions as well as "pseudorandom" (in some sense) examples, using "less" randomness than, say, filling every entry of a matrix with a random variable etc. For example - suppose we know that for a fixed norm an n x n matrix with IID standard gaussian entries has "large" norm with high probability. How to find an explicit infinite family of such matrices?</p> <p>My question is rather vague, of course I have a specific application of this kind of results in mind, but at this moment I am more interested in general methodology of constructing "derandomized" examples, where to start looking for such objects etc. My only contact so far with pseudorandomness has been in the context of spectral graph theory, expander graphs, property (T) etc., I'm not sure if this perspective is relevant for high-dimensional geometry.</p> <p>I'd be grateful for any hints, references or advice on who may know this kind of things.</p>

http://mathoverflow.net/questions/87711/derandomizing-random-matrices/87715#87715 Mark Meckes 2012-02-06T19:59:32Z 2012-02-08T20:30:35Z

<p>There is active interest in such results in high-dimensional geometry, and expander graphs have even been used explicitly as a tool. Take a look for example at <a href="http://arxiv.org/abs/1001.0041" rel="nofollow">this paper</a> and the references on the second page.</p> <p><strong>Added</strong>: After prodding from the OP, here are some more references to various results of this type. If this question manages to recapture Bill Johnson's attention, maybe he'll contribute some more that I didn't think of.</p> <p><a href="http://www.cwru.edu/artsci/math/szarek/TeX/DavSzaHB.pdf" rel="nofollow">Here</a> is a survey paper by Davidson and Szarek ending with a short section on derandomizing various constructions. As the Indyk&ndash;Szarek paper I linked to above shows, the discussion of Kashin-type results is definitely out of date, but it also has references to work on approximation of quasidiagonal operatrors and approximately free (in the sense of free probability) matrices; I don't know the state of the art on those things.</p> <p>Other results on reducing randomness in Kashin-type theorems (not all cited by Indyk&ndash;Szarek) followed <a href="http://arxiv.org/abs/math/0301275" rel="nofollow">this paper</a> by Schechtman; try a Google Scholar or MathSciNet search of the papers citing it.</p> <p><a href="http://www.tau.ac.il/~shiri/algandana/algandana.pdf" rel="nofollow">This paper</a> by Artstein-Avidan and Milman includes results on reducing randomness in a number of different theorems in geometric functional analysis.</p> <p>As I said in comments below, randomness reduction is a hot topic in compressed sensing, and not being an expert in the area I don't dare try to guess at the quickly-moving state of the art.</p> <p>All of the above results, although not necessarily explicitly stated that way, can of course be phrased in terms of properties of some matrices (e.g., identifying a subspace with a matrix whose columns are a basis for the subspace).</p>