¿Puede la matriz de medida utilizada para la detección compresiva ser una matriz dispersa?

Question

Me interesa analizar Mecanismo de compresión: Utilización de la representación dispersa en la privacidad diferencial . En mi investigación, la matriz de medición $A\mathbb \in R^{m \times n}$ debe ser escasa. El problema es que $n$ es potencialmente enorme, por ejemplo, puede ser mayor que $50,000,000,000$ . Por lo tanto, la dispersión es necesaria si la matriz se va a representar en memoria. Utilizando números de coma flotante de precisión simple, donde $m=\Theta(\log(n))$ Una matriz densa necesitaría más de 6.000 gigabytes de memoria.

Intenté buscar construcciones dispersas para la matriz de medición, pero no aparece bien en Google; la palabra "dispersa" es bastante común en la literatura sobre detección compresiva. También descubrí que la propiedad de isometría restringida no es la única propiedad suficiente para la detección compresiva [2], lo que dificulta aún más la búsqueda.

Para mis propósitos, sería igualmente bueno encontrar una construcción dispersa para la matriz de medida, o alternativamente descubrir que tal construcción es computacionalmente inviable (NP-difícil, en el espíritu de [3] y [4]), por lo que puedo descartar este método por completo.

[2] B.S. Kashin y V.N.Temlyakov, A Remark on Compressed Sensing

[3] Afonso S. Bandeira, Edgar Dobriban, Dustin G. Mixon, William F. Sawin, Certifying the Restricted Isometry Property is Hard

[4] Andreas M. Tillmann, Marc E. Pfetsch, The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing (La complejidad computacional de la propiedad de isometría restringida, la propiedad de espacio nulo y conceptos relacionados en la detección comprimida).

Answer 1

Estas son las construcciones que enumeré hace un tiempo [1]:

• Los conjuntos RIP(1) de Indyk et al.
• Las transformadas Johnson-Lindenstrauss dispersas ,
• Proyecciones aleatorias amistosas de la base de datos de Achioloptas
• Las matrices "mágicas" de Krzakala et al (véase también su reciente ampliación)
• El diseño chino ligero
• La construcción determinista LDPC de Dimakis et al.
• Las matrices incoherentes binarias de Bailey, Iwen y Spencer (estas matrices son dispersas cuando se multiplican con una matriz de transformada discreta de Fourier

)

[1] http://nuit-blanche.blogspot.com/2012/03/sparse-measurement-matrices-what-are.html

Answer 2

Hay artículos en los que se demuestra que, con una configuración adecuada, las matrices gaussianas dispersas también funcionan bien y se dispone de bouds bien conocidos.

Sin embargo se puede construir una matriz de detección densa aleatoria multiplicando una matriz de permutación dft like matrix y una matriz de raspado. Puedes buscar en google matrices estructuralmente aleatorias.