Structure Tensors

publicado: 5 sep. 2017  |  
540visits
No s'ha trobat cap mèdia.
Sinopsis
Compartir
Descargar
Comentarios (0)
  • We show that in many instances, at the heart of a problem in numerical computation sits a special 3-tensor, the structure tensor of the problem that uniquely determines its underlying algebraic structure. For example, the Grothendieck constant, which plays an important role in unique games conjecture and SDP relaxations of NP-hard problems, arises as the spectral norm of such a structure tensor. In matrix computations, a decomposition of the structure tensor into rank-1 terms gives an explicit algorithm for solving the problem, its tensor rank gives the speed of the fastest possible algorithm, and its nuclear norm gives the numerical stability of the stablest algorithm. As an explicit example, we determine the fastest algorithms for the basic operation underlying Krylov subspace methods <the structured matrix-vector products for sparse, banded, triangular, symmetric, circulant, Toeplitz, Hankel, Toeplitz-plus-Hankel, BTTB matrices> by analyzing their structure tensors. Our method is a generalization of the Cohn--Umans method, allowing for arbitrary bilinear operations in place of matrix-matrix product, and arbitrary algebras (e.g., coordinate rings of schemes, cohomology rings of manifolds, PI algebras) in place of group algebras. The second part is joint work with Ke Ye.

    Presentation by: Lek-Heng Lim. University of Chicago, USA

    Llicència Creative Commons by-nc-nd
    Notificar
    Alerta de contenido erróneoCerrar
    Si heu detectat algún error a aquest vídeo ens ho podeu notificar al correu mencionant l'identificador del vídeo: 115209
    ©Universitat de Barcelona
  • Codi per incrustar aquest vídeo
  • Para descargar los ficheros haz clic en "Botón derecho" sobre el enlace y "Guardar enlace como".
Pàgina