CS: Tilings, Islamic Art, Our Retina, Papoulis Sub-Nyquist Theorem

[Note: This is an open ended entry, sorry, I am trying to put these pieces together ]

As a I was re-reading Yves Meyer's recent presentation entitled: Compressed sensing and transference (the paper is here "A variant of compressed sensing "), I also came across his reference to some Islamic Art. If you recall, Yves Meyer has looked at quasicrystals tiling and has seen a connection with how to sample a positive function and reconstruct it with a linear programming step. It so happens that the connection between quasicrystals and Islamic art was made by Peter Lu as a hobby while being a graduate student. He has a beautiful video presentation on the subject of Quasicrystals in Medieval Islamic Architecture.

I liked the connection to the non-sticking pan material that messes up the phonon transport. At 45 minutes in the presentation, Paul begins to explain the non-periodic aspect of these tilings and the last question by a person in the audience is potentially of interest when it comes to sampling on manifolds.

The Science paper is here and the additional material is here. Paul Steinhardt the co-author of the study has a webpage on the tiling description and goes on to say in the "implications" section:

The new paradigm implies a closer physical relationship between quasicrystals and crystals. Now it appears that both can be described in terms of the close-packing of a single cluster or unit cell. In a crystal, the unit cell packs edge-to-edge with its neighbors. Quasicrystals correspond to a generalization in which the quasi-unit cells overlap. In both cases, the formation of the particular structure appears to be explained by a low-energy atomic cluster, although the atomic arrangement in the case of quasicrystals is constrained to allow overlap. Hence, the new paradigm makes plausible why many materials form quasicrystals and, at the same time, explains why quasicrystals are less common than crystals.....The new paradigm requires a mechanism to explain how quasicrystals grow. If the quasicrystals are grown slowly, then thermodynamic relaxation to the ground state is possible. However, some of the most perfect quasicrystal samples, including AlNiCo , are formed by rapid quenching. In this volume, Socolar has described a scheme for solids equivalent to Penrose patterns based on obtuse and acute rhombi using vertex rules and stochastic growth similar to diffusion limited aggregation. This approach can be adapted to overlapping clusters. (Janot[13] has already suggested a similar mechanism for overlapping clusters, although his vertex rules allow random tilings as well as perfect quasiperiodic tilings.) If quasicrystals form due to a particular cluster being energetically favored, a simpler kinematic mechanism may be through local atomic rearrangement that increases the local density of the given atomic cluster.

Hmmm, so we don't have a good way of explaining away the difference between random tilings and quasicrystal ones. Looks like we have a similar issue in compressive sampling where the connection between the tiling of Yves Meyer and Basarab Matei is not well connected to the generic random projections used in generic compressive sensing (expect maybe through the suggestion of Thong Do, Trac Tran and Lu Gan to include them in Structurally Random Matrices approach, in this case the analog FFT is performed by the lens). Furthermore, we also still have to characterize if our own pixel tiling located in our retina is also really that random as seen in these exceptional shots from Austin Roorda at Berkeley [17].

where it can be noted some type of hexagonal tiling in the Fourier world [16]

While reading these papers, a paper by Yue M. Lu, Minh Do and Richard Laugesen came out. It is entitled:



A computable Fourier condition generating alias-free sampling lattices. The abstract reads:

We propose a Fourier analytical condition linking alias-free sampling with the Fourier transform of the indicator function defined on the given frequency support. Our discussions center around how to develop practical computation algorithms based on the proposed analytical condition. We address several issues along this line, including the derivation of simple closed-form expressions for the Fourier transforms of the indicator functions defined on arbitrary polygonal and polyhedral domains; a complete and nonredundant enumeration of all quantized sampling lattices via the Hermite normal forms of integer matrices; and a quantitative analysis of the approximation of the original infinite Fourier condition by using finite computations. Combining these results, we propose a computational testing procedure that can efficiently search for the optimal alias-free sampling lattices for a given polygonal or polyhedral shaped frequency domain. Several examples are presented to show the potential of the proposed algorithm in multidimensional filter bank design, as well as in applications involving the design of efficient sampling patterns for multidimensional bandlimited signals.

an extract of this paper reads:

On a broader scale, alias-free sampling is mathematically equivalent to the lattice packing of a given domain, for which lots of studies can be found in disciplines such as computational geometry and operational research. So far, most practical algorithms proposed for densest lattice packing (e.g. [14]–[16]) approach the problem from a geometrical perspective. The primary tools employed are the theories from Minkowski’s work [13], as well as various geometrical intuitions and heuristics obtained for particular domains in lower dimensions......Before proceeding, we make some remarks on the scope of this paper. First, we restrict our attention to the scenario in which the continuous signals are sampled on a single lattice. Consequently, the minimum sampling rate we pursue is the Nyquist rate, which is achieved by those lattices that can pack the frequency support D in the tightest way. We note that it is possible to go below the Nyquist rate if we can sample the continuous signals with multiple channels and on multiple lattices (see, e.g., [19], [20]).

Let us recall that the subdivision scheme in the quasicrystal presentation seem to clearly fall under the class of multiple lattices. When doing a search on the IEEE xplore database reference 1 through 15 show up when refering to the 1977 Papoulis' Generalized sampling expansion [5]. I note a hardware based on this sub-nyquist sampling approach in [15]. I still cannot make much of it, so if somebody has an insight, I would gladly welcome it.

Talking about Compressive Sampling, the Computer Science Department at University of Alberta has a reading group on the subject.

References:

1. On well-posedness of the Papoulis generalized sampling expansion, Brown, J.L., Jr.; Cabrera, S.D.; Circuits and Systems, IEEE Transactions on, Volume 38, Issue 5, May 1991 Page(s):554 - 556

2. Generalized sampling expansion on lattices, Izen, S.H.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], Volume 53, Issue 6, June 2005 Page(s):1949 - 1963

3. Optimal generalized sampling expansion, Seidner, D.; Feder, M.; Acoustics, Speech, and Signal Processing, 1999. ICASSP '99. Proceedings., 1999 IEEE International Conference on, Volume 3, 15-19 March 1999 Page(s):1637 - 1640 vol.3

4. On the necessity of Papoulis' result for multidimensional GSE, Feuer, A.; Signal Processing Letters, IEEE. Volume 11, Issue 4, April 2004 Page(s):420 - 422

5. Generalized sampling expansion, Papoulis, A.; Circuits and Systems, IEEE Transactions on, Volume 24, Issue 11, Nov 1977 Page(s):652 - 654

6. Extension of a finite version of the sampling theorem, De Sabata, A.; Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on. Volume 41, Issue 12, Dec. 1994

7. Incomplete sampling series and the recovery of missing samples from oversampled band-limited signals, Ferreira, P.J.S.G.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on]
Volume 40, Issue 1, Jan. 1992 Page(s):225 - 227

9. Filterbank reconstruction of bandlimited signals from nonuniform and generalized samples, Eldar, Y.C.; Oppenheim, A.V.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on, Volume 48,
Issue 10, Oct. 2000 Page(s):2864 - 2875

10. Vector sampling expansion, Seidner, D.; Feder, M.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on] Volume 48, Issue 5, May 2000 Page(s):1401 - 1416

11. Filter bank interpolation and reconstruction from generalized and recurrent nonuniform samples, Eldar, Y.C.; Oppenheim, A.V.; Acoustics, Speech, and Signal Processing, 2000. ICASSP '00. Proceedings. 2000 IEEE International Conference on, Volume 1, 5-9 June 2000 Page(s):324 - 327 vol.1

12. 3D super-resolution using generalized sampling expansion, Shekarforoush, H.; Berthod, M.; Zerubia, J.; Image Processing, 1995. Proceedings., International Conference on, Volume 2, 23-26 Oct. 1995 Page(s):300 - 303 vol.2

13. Sampling reconstruction of N-dimensional band-limited images after multilinear filtering, Brown, J.L., Jr.; Sa-ngsari, K.; Circuits and Systems, IEEE Transactions on Volume 36, Issue 7, July 1989 Page(s):1035 - 1038

14. On generalized sampling expansions for deterministic signals, Figueiras-Vidal, A.; Marino-Acebal, J.; Gomez, R.; Circuits and Systems, IEEE Transactions on Volume 28, Issue 2, Feb 1981 Page(s):153 - 154

15. Sampling below the Nyquist rate in interferometric fluorescence microscopy with multi-wavelength measurements to remove aliasing, Davis, B.J.; Karl, W.C.; Goldberg, B.B.; Swan, A.K.; Unlu, M.S.; Digital Signal Processing Workshop, 2004 and the 3rd IEEE Signal Processing Education Workshop. 2004 IEEE 11th, 1-4 Aug. 2004 Page(s):329 - 333

16. Duncan,J.L., Zhang,Y., Gandhi,J., Nakanishi,C., Othman,M., Branham,K.H., Swaroop,A., Austin Roorda High resolution imaging of foveal cones in patients with inherited retinal degenerations using adaptive optics, Invest.Ophthalmol.Vis.Sci. 48: 3283-3291 (2007)

17. Austin Roorda, A., Williams, D.R., The Arrangement of the Three Cone Classes in the Living Human Eye Nature 397, 520-522 (1999).