The Johnson-Lindenstrauss lemma shows how to project points in much lower dimension without significant distortion of their pairwise Euclidean distances.
Say you have n arbitrary vectors 
Use a fat random (normalized) Gaussian matrix of dimensions 
to project the points in m dimensions.
Then, with probability at least 1/2, the projected points 
This is quite remarkable since we reduced the dimension from 
This is a very fat matrix.
A number of other matrices beyond Gaussian have been shown to also work with similar guarantees.
The Johnson-Lindenstrauss lemma sounds similar to the Restricted Isometry Property (RIP).
A fat
for all vectors 
This means that the matrix A does not distort the 
As before, well-known results have shown that random Gaussian matrices satisfy RIP with high probability if we set
To understand the similarities and differences between RIP and JL, we need to see how these results are proven. The central question is how fat random matrices distort the length of vectors and with what probability.
All known proofs of JL (for each matrix family) start with a lemma that deals with one fixed vector:
Lemma 1:
For each given vector
![Pr[ (1-\epsilon) ||x||_2 \leq ||Ax||_2 \leq (1+\epsilon) ||x||_2] \geq 1- P_{fail}(m,n) \quad (1)](https://s0.wp.com/latex.php?latex=Pr%5B+%281-%5Cepsilon%29+%7C%7Cx%7C%7C_2+%5Cleq+%7C%7CAx%7C%7C_2+%5Cleq+%281%2B%5Cepsilon%29+%7C%7Cx%7C%7C_2%5D+%5Cgeq+1-+P_%7Bfail%7D%28m%2Cn%29+%5Cquad+%281%29&bg=ffffff&fg=333333&s=0&c=20201002)
The key issue is between for all versus for each vector quantifiers.
If we first fix the vector and throw the matrix randomly, this is much easier than promising something for a random matrix that once realized, works w.h.p. for all vectors.
Clearly, if first realize the matrix, there are certainly vectors where lemma 1 cannot hold: since the matrix is fat, it has a nullspace so there are nonzero vectors that have 
How small we can make 
To prove JL for some family of matrices we need to make 
If we have lemma 1 with this guarantee, we just do a union bound over all 
It turns out that for Gaussian iid matrices, if you make 
To prove RIP, exactly the same recipe can be followed: first prove Lemma 1 for one vector and then do a union bound over all 
The general recipe emerges. Say you want to prove a good property for all hairy vectors.
First show that for each fixed vector a random matrix has the good property with probability at least 
Then ensure 
Finally, a union bound establishes the property for all hairy vectors.
regular graph will be a very high quality expander (for very small sets) and therefore a (very small) constant fraction of bit-flipping errors can be corrected by 
check nodes, if we take 
to be the incidence matrix of the bipartite graph (the parity check matrix of the code), we can form 
and look at its eigenvalues
and Tanner’s spectral bound on expansion is that expansion 
is greater than
for any size of expanding sets $\alpha$. Unfortunately this bound cannot certify expansion for any 
, which is exactly the point where it starts being useful for coding theory. Perhaps there are stronger spectral bounds that could establish more expansion, the book 
probability. This is what is refered to as ‘locally-tree like’. I do not know of any stronger statements but I think it can be easily shown that for any fixed cycle length, the expected number of cycles of that length is constant for regular random graphs.
bipartite expander graphs. But given a fixed measurement matrix how do we certify that it is good and should be implemented in a system?
measurements one recovers almost all sparse signals of size up to $0.05 n$ (whp over supports) and the 
measurement matrix has 
non-zeros. (see our recent 
distributed sources and they want to create a good erasure code in a network: a data collector who accesses any 
system is storing incorrect equations. These could be originating from bit-flipping errors in the storage medium or (more likely) if a malicious node was injecting errors during a previous repair in the storage system.
and only send the projections. The error detection works since the projected data follows the same 
using a small seed 
, and project on that. All the storage nodes need to share the small seed 
.
where 
is the total variation bound obtained from the pseudo-random generator.
nodes in an 
(sometimes also found as 
in the literature) one can use an 
, encode into 
) and store each packet into a storage node. The reliability achieved is that any 
failures without losing data. But most of the time we only have one failure. We then want to repair this failure by creating a new encoded packet by communicating as little information as possible from 
surviving storage nodes. There are two cases:
. Another issue is that one can reduce this repair bandwidth if the storage per node 
is allowed to increase and there is a tradeoff involved.
.
of failed nodes. The second result in this paper is that all the other interior points of the tradeoff curve (except the points of minimum repair and minimum storage) cannot be achieved with linear codes for exact repair. ( Of course this does not preclude the possibility that they can be approached infinitely close by making the code packets smaller and smaller).
if the number of nodes helping for the repair is sufficiently large 
, the MSR cut-set point can be achived for exact repair. For this regime the paper presents explicit code constructions that use a small finite fields and build on 
regime. The paper uses the symbol extension technique introduced in the Cadambe-Jafar paper 
.
(without allowing backtracking) of this graph, consisting of edges 
, define a monomial 
that is the product of terms 
for all the edges of the cycle.
.
An Ergodic Walk 