Stephen A. Vavasis

Stephen A. Vavasis

Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases and other information retrieval and clustering applications. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists.

Brendan P. W. Ames, Stephen A. Vavasis

We consider the k-disjoint-clique problem. The input is an undirected graph G in which the nodes represent data items, and edges indicate a similarity between the corresponding items. The problem is to find within the graph k disjoint cliques that cover the maximum number of nodes of G. This problem may be understood as a general way to pose the classical `clustering' problem. In clustering, one is given data items and a distance function, and one wishes to partition the data into disjoint clusters of data items, such that the items in each cluster are close to each other. Our formulation additionally allows `noise' nodes to be present in the input data that are not part of any of the cliques. The k-disjoint-clique problem is NP-hard, but we show that a convex relaxation can solve it in polynomial time for input instances constructed in a certain way. The input instances for which our algorithm finds the optimal solution consist of k disjoint large cliques (called `planted cliques') that are then obscured by noise edges and noise nodes inserted either at random or by an adversary.

Gun Srijuntongsiri, Stephen A. Vavasis

This article considers the problem of solving a system of $n$ real polynomial equations in $n+1$ variables. We propose an algorithm based on Newton's method and subdivision for this problem. Our algorithm is intended only for nondegenerate cases, in which case the solution is a 1-dimensional curve. Our first main contribution is a definition of a condition number measuring reciprocal distance to degeneracy that can distinguish poor and well conditioned instances of this problem. (Degenerate problems would be infinitely ill conditioned in our framework.) Our second contribution, which is the main novelty of our algorithm, is an analysis showing that its running time is bounded in terms of the condition number of the problem instance as well as $n$ and the polynomial degrees.

Stephen A. Vavasis

We present a gradient-based algorithm for unconstrained minimization derived from iterated linear change of basis. The new method is equivalent to linear conjugate gradient in the case of a quadratic objective function. In the case of exact line search it is a secant method. In practice, it performs comparably to BFGS and DFP and is sometimes more robust.

Gun Srijuntongsiri, Stephen A. Vavasis

In [5], Srijuntongsiri and Vavasis propose the "Kantorovich-Test Subdivision algorithm", or KTS, which is an algorithm for finding all zeros of a polynomial system in a bounded region of the plane. This algorithm can be used to find the intersections between a line and a surface. The main features of KTS are that it can operate on polynomials represented in any basis that satisfies certain conditions and that its efficiency has an upper bound that depends only on the conditioning of the problem and the choice of the basis representing the polynomial system. This article explores in detail the dependence of the efficiency of the KTS algorithm on the choice of basis. Three bases are considered: the power, the Bernstein, and the Chebyshev bases. These three bases satisfy the basis properties required by KTS. Theoretically, Chebyshev case has the smallest upper bound on its running time. The computational results, however, do not show that Chebyshev case performs better than the other two.

Sina Baghal, Courtney Paquette, Stephen A. Vavasis

We propose a new, simple, and computationally inexpensive termination test for constant step-size stochastic gradient descent (SGD) applied to binary classification on the logistic and hinge loss with homogeneous linear predictors. Our theoretical results support the effectiveness of our stopping criterion when the data is Gaussian distributed. This presence of noise allows for the possibility of non-separable data. We show that our test terminates in a finite number of iterations and when the noise in the data is not too large, the expected classifier at termination nearly minimizes the probability of misclassification. Finally, numerical experiments indicate for both real and synthetic data sets that our termination test exhibits a good degree of predictability on accuracy and running time.

Nicolas Gillis, Stephen A. Vavasis

The low-rank matrix approximation problem with respect to the component-wise $\ell_1$-norm ($\ell_1$-LRA), which is closely related to robust principal component analysis (PCA), has become a very popular tool in data mining and machine learning. Robust PCA aims at recovering a low-rank matrix that was perturbed with sparse noise, with applications for example in foreground-background video separation. Although $\ell_1$-LRA is strongly believed to be NP-hard, there is, to the best of our knowledge, no formal proof of this fact. In this paper, we prove that $\ell_1$-LRA is NP-hard, already in the rank-one case, using a reduction from MAX CUT. Our derivations draw interesting connections between $\ell_1$-LRA and several other well-known problems, namely, robust PCA, $\ell_0$-LRA, binary matrix factorization, a particular densest bipartite subgraph problem, the computation of the cut norm of $\{-1,+1\}$ matrices, and the discrete basis problem, which we all prove to be NP-hard.

Nicolas Gillis, Stephen A. Vavasis

Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exists a cone spanned by a small subset of the columns of the input nonnegative matrix approximately containing all columns. In this paper, we propose a preconditioning based on semidefinite programming making the input matrix well-conditioned. This in turn can improve significantly the performance of near-separable NMF algorithms which is illustrated on the popular successive projection algorithm (SPA). The new preconditioned SPA is provably more robust to noise, and outperforms SPA on several synthetic data sets. We also show how an active-set method allow us to apply the preconditioning on large-scale real-world hyperspectral images.

Nicolas Gillis, Stephen A. Vavasis

In this paper, we study the nonnegative matrix factorization problem under the separability assumption (that is, there exists a cone spanned by a small subset of the columns of the input nonnegative data matrix containing all columns), which is equivalent to the hyperspectral unmixing problem under the linear mixing model and the pure-pixel assumption. We present a family of fast recursive algorithms, and prove they are robust under any small perturbations of the input data matrix. This family generalizes several existing hyperspectral unmixing algorithms and hence provides for the first time a theoretical justification of their better practical performance.

Stephen A. Vavasis

We conjecture that the roots of a degree-n univariate complex polynomial are located in a union of n-1 annuli, each of which is centered at a root of the derivative and whose radii depend on higher derivatives. We prove the conjecture for the cases of degrees 2 and 3, and we report on tests with randomly generated polynomials of higher degree. We state two other closely related conjectures concerning Newton's method. If true, these conjectures imply the existence of a simple, rapidly convergent algorithm for finding all roots of a polynomial.