IEEE Transactions on Pattern Analysis and Machine Intelligence

A primary computational problem in kernel regression is solution of a dense linear system with the N × N kernel matrix.Because a direct solution has an O(N 3 ) cost, iterative Krylov methods are often used with fast matrix-vector products.For poorly conditioned problems, convergence of the iteration is slow and preconditioning becomes necessary.We investigate preconditioning from the viewpoint of scalability and efficiency.The problems that conventional preconditioners face when applied to kernel methods are demonstrated.A novel flexible preconditioner that not only improves convergence but also allows utilization of fast kernel matrixvector products is introduced.The performance of this preconditioner is…

• NS
  National Science Foundation

  Awards: 0403313, 403313
• N
  Nvidia
• NO
  National Oceanic and Atmospheric Administration