Search For:

Displaying 1-7 out of 7 total
Fast and Robust Recursive Algorithmsfor Separable Nonnegative Matrix Factorization
Found in: IEEE Transactions on Pattern Analysis and Machine Intelligence
By Nicolas Gillis,Stephen A. Vavasis
Issue Date:April 2014
pp. 698-714
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 ...
Exponential lower bounds for finding Brouwer fixed points
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Michael D. Hirsch, Stephen Vavasis
Issue Date:October 1987
pp. 401-410
The Brouwer fixed point theorem has become a major tool for modeling economic systems during the 20th century. It was intractable to use the theorem in a computational manner until 1965 when Scarf provided the first practical algorithm for finding a fixed ...
Nonnegative matrix factorization via rank-one downdate
Found in: Proceedings of the 25th international conference on Machine learning (ICML '08)
By Ali Ghodsi, Michael Biggs, Stephen Vavasis
Issue Date:July 2008
pp. 64-71
Nonnegative matrix factorization (NMF) was popularized as a tool for data mining by Lee and Seung in 1999. NMF attempts to approximate a matrix with nonnegative entries by a product of two low-rank matrices, also with nonnegative entries. We propose an alg...
An aspect ratio bound for triangulating a d-grid cut by a hyperplane (extended abstract)
Found in: Proceedings of the twelfth annual symposium on Computational geometry (SCG '96)
By Scott A. Mitchell, Stephen A. Vavasis
Issue Date:May 1996
pp. 48-57
An interactive visualization of weighted three-dimensional α-hulls is presented for static and dynamic spheres. The α-hull is analytically computed and represented by a triangulated mesh. The entire surface is computed and displayed in real-time ...
An accelerated interior point method whose running time depends only on A (extended abstract)
Found in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (STOC '94)
By Stephen A. Vavasis, Yinyu Ye
Issue Date:May 1994
pp. 512-521
We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint v...
Quality mesh generation in three dimensions
Found in: Proceedings of the eighth annual symposium on Computational geometry (SCG '92)
By Scott A. Mitchell, Stephen A. Vavasis
Issue Date:June 1992
pp. 212-221
We show how to triangulate a three dimensional polyhedral region with holes. Our triangulation is optimal in the following two senses. First, our triangulation achieves the best possible aspect ratio up to a constant. Second, for any other triangulation of...
Separators for sphere-packings and nearest neighbor graphs
Found in: Journal of the ACM (JACM)
By Gary L. Miller, Shang-Hua Teng, Stephen A. Vavasis, William Thurston
Issue Date:January 1988
pp. 1-29
A collection of n balls in d dimensions forms a k-ply system if no point in the space is covered by more than k balls. We show that for every k-ply system Γ, there is a sphere S that intersects at most O(k1/dn1−1/d) balls of Γ and divides t...