Rápido cálculo/estimación de la central nuclear de norma de una matriz

Question

La central nuclear de norma de una matriz se define como la suma de sus valores singulares, dado por la Descomposición de Valor Singular de la matriz. Es de central importancia en el Procesamiento de la Señal y de la Estadística, donde se utiliza para la finalización de la matriz y de la reducción de dimensionalidad. Una pregunta que tengo es si es posible calcular la norma de una matriz dada más rápido que el tiempo necesario para el cálculo de la svd. Ya no necesitamos todos los valores singulares, pero sólo la suma de los mismos, esto parece posible. Alternativamente, tal vez podría ser posible aproximar con métodos de simulación y/o aleatoria de las proyecciones.

Answer 1

Desde que pidió una aproximación así, usted podría encontrar que el papel de "Algunos simples cálculos para los valores singulares de una matriz" por Liqun Qi útil. Hay algunas buenas estimaciones de allí.

Sin embargo, si estos no son precisas para usted, usted podría considerar la posibilidad de informática de enfermedad vesicular porcina con una baja precisión, es decir, hacer una o dos o tres iteraciones y, a continuación, utilizar las estimaciones anteriores. Dependiendo del tamaño de sus matrices, esto puede dar una buena aceleración.

Dado que las estimaciones son de la forma $\sigma_i \in [ a_i, b_i ]$, usted también tendrá una estimación de error, por lo que usted puede hacer iteraciones de enfermedad vesicular porcina el cálculo hasta que el error absoluto $\sum_i (b_i - a_i)$, o algunos de sus relativa homólogos, es lo suficientemente pequeño.

Aparte de eso, no creo que hay mucho por hacer. SVD existe para evitar el cálculo de $A^*A$ cuando se desee que estos valores propios, por lo que estos trucos no ayuda, a menos que sus matrices tienen algunas buenas propiedades que no mencionó.

Las estimaciones y aproximaciones son realmente no es mi área de interés, así que tal vez no son los resultados de la más reciente que la de arriba del papel.

Answer 2

Esto es sólo una suposición, pero ya que la suma de los valores propios de a es el maximimum de tr(A*U) donde U es ortogonal, podría ser capaz de estimar mediante el cálculo de la máxima barriendo las rotaciones de givens ?

El máximo, más de theta de Tr( A*G(i,j,theta) es

Tr(A) + hypot(A(i,i)+A(j,j), (i,j)-{j,i)) - A(i,i) - A(j,j)

Si este supera Tr(A), se puede reemplazar con Un*G(i,j,theta^) y probar con otro i,j.

Answer 3

Una respuesta tentativa: la nuclear norma de $A$ es la traza de $\sqrt{A^*A}$ donde $A^*$ es el conjugado-transpuesta de a $A$, e $\sqrt{\cdot}$ es la matriz de la raíz cuadrada. Así que siempre se puede calcular la matriz de raíces cuadradas más rápido que la descomposición de valor singular, esto podría ser útil.