Thread by @_rax

Voy a tratar de explicar qué gracia tienen los algoritmos usados para la reconstrucción que permitió obtener la imagen que publicó el EHT. Pero para eso tengo que partir en 1807 con un Señor llamado Joseph Fourier. Ah, y todo esto es culpa de @borelian por sacudirme la jaula.

Ese año Fourier publicó un artículo demostrando que las señales pueden ser escritas como una suma de funciones trigonométricas. Años antes ya Gauss y Lagrange (otro par de gigantes en matemáticas) lo habían hecho para señales particulares, pero Fourier dijo TODAS.

Y su apellido es una forma de ver el mundo: la Transformada de Fourier. Con este lente, vemos cualquier señal (función) como una suma de senos/cosenos de diferentes frecuencias. Acá un GIF que muestra la descomposición.
visualizingmath.tumblr.com/post/639624738…

Mientras más “brusca” es la señal, se necesitan frecuencias más altas para lograr esos bordes. Si eliminamos las altas frecuencias, las cosas se ven más suaves o borrosas. Eso es lo clave del formato JPG por ejemplo: borrar las altas frecuencias en la foto.

Saltamos a 1949, donde Claude Shannon (otro matemático, padre de la teoría de la información) mostró que, para poder reconstruir en forma perfecta una señal, debíamos sacar muestras al menos al doble de su máxima frecuencia. Esto se conoce como el teorema de Shannon-Nyquist.

Así, si queremos ver algo con el doble de resolución, no nos queda más que sacar el doble de muestras. De lo contrario, se produce un fenómeno llamado “aliasing” donde se solapan las altas frecuencias y no se puede reconstruir la señal en forma unívoca ej: en.wikipedia.org/wiki/Aliasing

Y así vivimos hasta 2007, cuando Emmanuel Candes, Terence Tao, Justin Romberg y David Donoho (todos trabajando en matemáticas), mostraron que podíamos hacer más. Shannon mostró que no había una única forma de reconstruir una señal si tenemos pocas muestras...

… y como buenos matemáticos, buscaron cómo vadear la letra chica: el teorema decía “única”. Quizá no eran tantas las posibles señales que podían resultar de esas pocas muestras y era cosa de buscar “la mejor”

Resulta que las señales en la vida real tienen “poca información”. Esta imagen de “ruido” tiene un montón de información: no puedo adivinar el valor de un píxel por el valor de los pixeles cercanos. Tengo que detallar el valor de cada uno.

En cambio, las señales de la vida real (y las imágenes en particular) tienen mucha estructura y la cantidad de información es menor. Me basta con un par de trazos y puedo adivinar el contenido completo de la imagen (por eso podemos comprimir harto las imágenes que sacamos)

Así nació "compressed sensing" y la idea central es encontrar la señal más simple que genera esas muestras que tenemos. “simple” en este caso era la señal menos densa, también llamada “sparse”, es decir, buscamos la señal con más ceros.

Lograr esto se reduce a resolver un problema de optimización en la llamada norma L0, algo muy difícil pues esta cosa ni siquiera cumple con las reglas básicas que cumplen todas las otras normas en matemáticas.

Llevamos siglos resolviendo problemas en la norma L2, que no es más que el error cuadrático medio. Gauss lo hizo para regresiones lineales y un montón de técnicas buscan reducir esa medida de error para entrenar algoritmos. Pero L0 es un bicho totalmente distinto.

Pero Candes y Tao mostraron que, para un montón de problemas, resolver este problema de optimización en L0, era igual a resolverlo en norma L1 (valor absoluto para los mortales). Algo que ya podemos resolver en forma más fácil.

<dato al margen> esto mostró ser tremendamente útil para resolver problemas de “machine learning” con lo que nacieron las regresiones lasso y técnicas similares que minimizan en norma L1. <fin dato al margen>

Para mostrar que se podía llevar a la práctica, Richard Baraniuk y Kevin Kelly construyeron una cámara de un puro pixel y que bastaba moverlo un poco para reconstruir la imagen completa.

No era práctico para cámaras de fotos comunes, donde los pixeles son muy baratos, pero un tremendo avance para cuando los pixeles con caros, como en infrarrojo, radio, etc

Y llegamos al Event Horizon Telescope. Para poder ver la sombra del agujero negro, necesitaban una resolución de 20 micro arcosegundos. Eso es equivalente a poder leer la leyenda de una foto del diario, con el diario en el Morro de Arica y uno sentado en Puerto Williams.

Para eso se necesita una antena del porte del planeta, o llenar el planeta de antenas. Pero, con la misma lógica de compressed sensing, quizá nos basta con unos pocos “pixeles importantes” para recuperar toda la imagen.

El problema se complica al ser sólo 8 telescopios los “pixeles” que están funcionando. Así que el equipo del EHT desarrolló diferentes algoritmos para poder reconstruir la señal con tan pocas muestras. Varios grupos trabajaron en forma independiente para lograr esto.

En particular, se desarrollaron siete algoritmos que usan “priors”, es decir, sacan estructura de imágenes reales para buscar la solución que mejor representa las muestras obtenidas, pero que también se parece a estas imágenes reales. iopscience.iop.org/article/10.384…

La famosa imagen fue hecha con dos de esos siete: eht-imaging (por Chael et al. github.com/achael/eht-ima…) y SMILI (por Akiyama et al. github.com/astrosmili/smi…) Son open source así que pase a jugar si quiere.

¿Y qué importancia tiene todo esto? Es otro paso más para lograr hacer más con menos. Este tipo de algoritmos nos podría permitir sacar un décimo de las muestras en una resonancia magnética y obtener una imagen de la misma calidad… y eso implicaría un décimo del tiempo o costo.

La misma tecnología serviría en radares, tomografías, y etc., donde los costos o tiempos de cada muestra son altos y reducirlos nos ayudaría a todos.

FIN