CS: LSH, Photon Sieves, Fieldstream

Sergey Ten asks the following question on Twitter:

Are there connection between locality sensitive hashing and compressed sensing ? (RIP)

My take is that one could use random projections to reduce a very high dimensional dataset onto some lower dimensional manifold and then probably use LSH to evaluate how these reduced data are connected to each other. Piotr Indyk on his LSH page makes a different case in the presentation entitled: Near-Optimal Hashing Algorithms for Approximate Near(est) Neighbor Problem, where the following slide appear:

On a related item, Piotr also taught some course at Rice last year, the list of presentation can be found below:

These are the lecture notes for a short course "Streaming etc.", given at Rice University in Spring'09.

• Introduction to streaming algorithms. Estimating the number of distinct elements and the L0 norm.
  
  
• Estimating the L2 norm.
  
  
• Estimating the Lp norms using p-stable distributions.
  
  
• Heavy hitters and sparse approximations.
  
  
• Compressive sensing. Sparse recovery using sparse matrices. RIP1 principle. State of the art table.
  
  
• Lower bounds for streaming and compressed sensing.

Laurent Jacques mentioned to me the use of coded aperture to perform X-ray focusing. As you recall Gerry Skinner, a specialist in coded aperture, does not like coded aperture for imaging x-rays and this is the reason he is looking into Fresnel lenses for x-rays. As it turns out a way of providing additional focus for x-rays is by drilling holes in Fresnel lenses.


Instead of just using Fresnel Zone plates, they drill a (random ?) distribution of points on them:

Light passing a circular pinhole produces a diffraction pattern of concentric rings of decreasing width with increasing radius. If light is passed through a mask made up of the same pattern of rings a focus is formed. These Fresnel zone plates are used to focus soft X-rays where conventional optics fail because of strong absorption of all materials in this spectral region.

The ultimate resolution of a Fresnel zone plate is determined by the width of the outermost zone. The focal spot is surrounded by rings of intensity (secondary maxima) that blur the images obtained in X-ray microscopy and scanning spectroscopy.

These limitations can be overcome by using a large number of appropriately distributed pinholes instead of rings as the diffracting elements. To obtain a distinct first-order focus, the pinholes have to be positioned such that the optical path length from the source via the center of the pinholes to the focal point is an integral number of wavelengths.

Furthermore, with photon sieves, the unwanted ring-like secondary maxima generated by zone plates can be suppressed. For a zone plate each ring contributes equally to the amplitude in the focus. This contribution drops abruptly to zero beyond the outermost ring which leads to strong intensity oscillations in the diffraction pattern. With a photon sieve the number of pinholes per ring can be readily adjusted to yield a smooth transition which minimizes the secondary maxima.

Thanks Laurent.

Finally, the Google webcrawler just found the following recently funded project: Fieldstream. The compressive sensing part is currently empty. They seem to be connected to the Urban sensing project at UCLA.