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?

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.

I'd be grateful for any hints, references or advice on who may know this kind of things.


1 Answer 1


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 this paper and the references on the second page.

Added: 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.

Here is a survey paper by Davidson and Szarek ending with a short section on derandomizing various constructions. As the Indyk–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.

Other results on reducing randomness in Kashin-type theorems (not all cited by Indyk–Szarek) followed this paper by Schechtman; try a Google Scholar or MathSciNet search of the papers citing it.

This paper by Artstein-Avidan and Milman includes results on reducing randomness in a number of different theorems in geometric functional analysis.

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.

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).

  • $\begingroup$ And, as Mark knows well, this is only the tip of the iceberg. $\endgroup$ Feb 6, 2012 at 20:06
  • $\begingroup$ @Bill Johnson: if you have any suggestions for references or substantive comments, please consider putting them in an answer - that would be helpful! $\endgroup$ Feb 6, 2012 at 20:34
  • $\begingroup$ @Michal: For much more, and a demonstration that this circle of ideas is definitely a hot topic, I suggest googling "deterministic" along with either "compressed sensing" or "restricted isometry property". $\endgroup$ Feb 7, 2012 at 14:03
  • $\begingroup$ @Mark: thanks! Are there such constructions for other properties of random matrices apart from RIP (and stuff related to compressed sensing)? $\endgroup$ Feb 7, 2012 at 16:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .