El algoritmo más rápido para calcular el número de condición de una matriz grande en Matlab / Octave

A partir de la definición del número de condición, parece que se necesita una inversión de matriz para calcularlo, me pregunto si para una matriz cuadrada genérica (o mejor si es simétrica positiva definida) es posible explotar cierta descomposición de la matriz para calcular el número de condición en un forma más rápida

Calcular el número de condición (incluso aproximándolo dentro de un factor de 2) parece tener la misma complejidad que calcular una factorización, aunque no hay teoremas en esta dirección.

A partir de un factor disperso de Cholesky de una matriz definida positiva simétrica, o de una factorización dispersa (con implícita ) de una matriz cuadrada general, se puede obtener el número de condición en la norma de Frobenius calculando el subconjunto inverso disperso de , que es mucho más rápido que calcular el inverso completo. (Relacionado con este es mi artículo: Normas y límites híbridos para sistemas lineales sobredeterminados, Linear Algebra Appl. 216 (1995), 257-266. Http://www.mat.univie.ac.at/~neum/scan/74 .pdf )Q R Q ( R T R ) - $R$$QR$$Q$$(R^TR)^{-1}$

Editar: Si entonces con respecto a cualquier norma unitariamente invariante,Para el cálculo de factorizaciones QR dispersas, consulte, por ejemplo, http://dl.acm.org/citation.cfm?id=174408 . Para el cálculo del inverso escaso, ver, por ejemplo, mi artículo: Estimación de máxima verosimilitud restringida de covarianzas en modelos lineales dispersos, Genetics Selection Evolution 30 (1998), 1-24. https://www.mat.univie.ac.at/~neum/ms/reml.pdf El costo es aproximadamente 3 veces el costo de la factorización.c o n d ( A ) = c o n d ( R ) = $A=QR$

Ciertamente es fácil usar la descomposición del valor propio / vector propio de una matriz simétrica o la SVD de una matriz general para calcular el número de condición, pero estas no son formas particularmente rápidas de proceder.

Hay algoritmos iterativos que pueden calcular una estimación del número de condición que es útil para la mayoría de los propósitos sin tener que hacer todo el trabajo de calcular . Ver, por ejemplo, la función en MATLAB. $A^{-1}$condest

Para las matrices hermitianas dispersas , puede usar el algoritmo de Lanczos para calcular sus valores propios. Si no es Hermitiano, puede calcular sus valores singulares calculando los valores propios de .H H T$H$$H$$H^TH$

Dado que los valores propios / valores singulares más grandes y más pequeños se pueden encontrar muy rápido (mucho antes de que se complete la tridiagonalización), el método de Lanczos es particularmente útil para calcular el número de condición.