Aleatorización de Iteración de Subespacio y Problemas de Valor Singular

Un problema clásico en los cálculos de matrices es la aproximación eficiente y confiable de una matriz dada por una matriz de menor rango. Se sabe que la descomposición en valores singulares truncada (SVD) proporciona la mejor aproximación de este tipo para cualquier rango fijo dado. Sin embargo, también se conoce que la SVD es muy costosa de calcular. Entre los diferentes enfoques en la literatura para el cálculo de aproximaciones de bajo rango, los algoritmos aleatorizados han atraído recientemente la atención de los investigadores debido a su sorprendente confiabilidad y eficiencia computacional en diferentes áreas de aplicación. Típicamente, se muestra que tales algoritmos calculan con alta probabilidad aproximaciones de bajo rango que están dentro de un factor constante del óptimo, y se sabe que funcionan incluso mejor en muchas situaciones prácticas. En este artículo, presentamos un nuevo análisis de error que considera algoritmos aleatorizados dentro del marco de iteración de subespacios y mostramos con alta probabilidad que se pueden calcular rápidamente aproximaciones de bajo rango altamente precisas, así como valores singulares, para matrices con valores singulares que decaen rápidamente. Dichas matrices aparecen frecuentemente en diversas áreas de aplicación, como el análisis de datos, cálculos de matrices estructuradas rápidas y métodos directos rápidos para grandes sistemas lineales dispersos de ecuaciones, y son la motivación impulsora para los métodos aleatorizados. Además, mostramos que las aproximaciones de bajo rango calculadas por estos algoritmos aleatorizados son, de hecho, aproximaciones que revelan el rango, y el caso especial de una aproximación de rango 1 también se puede utilizar para estimar correctamente las 2-normas de matrices con alta probabilidad. Nuestros experimentos numéricos respaldan plenamente nuestras conclusiones.