Lek-Heng Lim – Optimization Online

Most tensor problems are NP-hard

Published: 2009/11/06, Updated: 2012/04/09

Applications - Science and Engineering, Global Optimization Theory, Graphs and Matroids #p-completeness, nonnegative definite tensors, np-hardness, numerical multilinear algebra, polynomial time approximation schemes, symmetric tensors, system of multilinear equations, tensor eigenvalue, tensor rank, tensor singular value, tensor spectral norm

We show that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list here includes: determining the feasibility of a system of bilinear equations, deciding whether a tensor possesses a given eigenvalue, singular value, or spectral norm; approximating an eigenvalue, eigenvector, singular vector, or spectral norm; determining a best … Read more

PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

Published: 2009/11/02, Updated: 2011/07/02

Ming Gu

Lek-Heng Lim

Cinna Julie Wu

Constrained Nonlinear Optimization, Convex Optimization, Optimization Software Benchmark accelerated proximal gradient methods, bpdn, compressed sensing, lasso, nesta, pareto curve, parnes, spgl1

In this article we propose an algorithm, NESTA-LASSO, for the LASSO problem (i.e., an underdetermined linear least-squares problem with a one-norm constraint on the solution) that exhibits linear convergence under the restricted isometry property (RIP) and some other reasonable assumptions. Inspired by the state-of-the-art sparse recovery method, NESTA, we rely on an accelerated proximal gradient … Read more

Quasi-Newton methods on Grassmannians and multilinear approximations of tensors

Published: 2009/08/03, Updated: 2010/05/30

Lek-Heng Lim

Berkant Savas

Data-Mining, Nonlinear Optimization approximations, grassmann bfgs, grassmann l-bfgs, grassmann manifold, grassmann quasi-newton, grassmannian, multilinear rank, product of grassmannians, symmetric multilinear rank, symmetric tensor, tensor

In this paper we proposed quasi-Newton and limited memory quasi-Newton methods for objective functions defined on Grassmannians or a product of Grassmannians. Specifically we defined BFGS and L-BFGS updates in local and global coordinates on Grassmannians or a product of these. We proved that, when local coordinates are used, our BFGS updates on Grassmannians share … Read more