An Almost Optimal Algorithm for Computing Nonnegative Rank

An Almost Optimal Algorithm for Computing Nonnegative Rank

Here, we give an algorithm for deciding if the nonnegative rank of a matrix M of dimension m \times n$ is at most r which runs in time (nm)[superscript O(r2)]. This is the first exact algorithm that runs in time singly exponential in r. This algorithm (and earlier algorithms) are built on methods f...

पूर्ण विवरण

ग्रंथसूची विवरण
मुख्य लेखक:	Moitra, Ankur
अन्य लेखक:	Massachusetts Institute of Technology. Department of Mathematics
स्वरूप:	लेख
भाषा:	en_US
प्रकाशित:	Society for Industrial and Applied Mathematics 2017
ऑनलाइन पहुंच:	http://hdl.handle.net/1721.1/108665 https://orcid.org/0000-0001-7047-0495

समान संसाधन

Lower bounds on nonnegative rank via nonnegative nuclear norms
द्वारा: Fawzi, Hamza, और अन्य
प्रकाशित: (2016)

Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank
द्वारा: Fawzi, Hamza, और अन्य
प्रकाशित: (2016)

Almost-optimal gossip-based aggregate computation
द्वारा: Chen, Jen-Yeu, और अन्य
प्रकाशित: (2013)

Vertex sparsification and universal rounding algorithms
द्वारा: Moitra, Ankur
प्रकाशित: (2011)

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size
द्वारा: Moitra, Ankur
प्रकाशित: (2010)

An exact penalty approach for optimization with nonnegative orthogonality constraints
द्वारा: Jiang, Bo, और अन्य
प्रकाशित: (2023)

Correntropy based nonnegative matrix factorization : algorithms and clustering applications
द्वारा: Peng, Siyuan
प्रकाशित: (2020)

Algorithmic foundations for the diffraction limit
द्वारा: Chen, Sitan, और अन्य
प्रकाशित: (2022)

On Rationality of Nonnegative Matrix Factorization
द्वारा: Chistikov, D, और अन्य
प्रकाशित: (2017)

Method of lines and conservation of nonnegativity
द्वारा: Vejchodský, T
प्रकाशित: (2004)

On restricted nonnegative matrix factorization
द्वारा: Kiefer, S, और अन्य
प्रकाशित: (2016)

Nonnegativity problems for matrix semigroups
द्वारा: D'Costa, J, और अन्य
प्रकाशित: (2024)

On restricted nonnegative matrix factorization
द्वारा: Chistikov, D, और अन्य
प्रकाशित: (2016)

Graphs with nonnegative resistance curvature
द्वारा: Devriendt, K
प्रकाशित: (2024)

Beyond the low-degree algorithm: mixtures of subcubes and their applications
द्वारा: Chen, Sitan, और अन्य
प्रकाशित: (2022)

Beyond the low-degree algorithm: mixtures of subcubes and their applications
द्वारा: Chen, Sitan, और अन्य
प्रकाशित: (2021)

On Nonnegative Matrix Factorization Algorithms for Signal-Dependent Noise with Application to Electromyography Data
द्वारा: Devarajan, Karthik, और अन्य
प्रकाशित: (2015)

Inverse problems with nonnegative and sparse solutions : algorithms and application to the phase retrieval problem
द्वारा: Muoi, Pham Quy, और अन्य
प्रकाशित: (2019)

Nonnegative matrix factorization requires irrationality
द्वारा: Chistikov, D, और अन्य
प्रकाशित: (2017)

Coefficient Conditions for Starlikeness of Nonnegative Order
द्वारा: M. Ali, Rosihan, और अन्य
प्रकाशित: (2012)

Combinatorics related to the totally nonnegative Grassmannian
द्वारा: Oh, SuHo
प्रकाशित: (2012)

On the number of nonnegative sums for certain function
द्वारा: Ku, Cheng Yeaw, और अन्य
प्रकाशित: (2022)

On the number of nonnegative sums for semi-partitions
द्वारा: Ku, Cheng Yeaw, और अन्य
प्रकाशित: (2022)

New algorithms for learning incoherent and overcomplete dictionaries
द्वारा: Arora, Sanjeev, और अन्य
प्रकाशित: (2016)

Optimal Distributed Algorithms for Sorting and Ranking
द्वारा: Zaks, Shmuel
प्रकाशित: (2023)

Almost primes in almost all short intervals
द्वारा: Teräväinen, J
प्रकाशित: (2016)

Nonnegative matrix factorization and metamorphic malware detection
द्वारा: Ling, Yeong Tyng, और अन्य
प्रकाशित: (2019)

On nonnegative integer matrices and short killing words
द्वारा: Kiefer, S, और अन्य
प्रकाशित: (2021)

Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
द्वारा: Golowich, Noah, और अन्य
प्रकाशित: (2024)

Information theoretic properties of Markov Random Fields, and their algorithmic applications
द्वारा: Hamilton, Linus Ulysses, और अन्य
प्रकाशित: (2018)

Vertex Sparsifiers and Abstract Rounding Algorithms
द्वारा: Charikar, Moses, और अन्य
प्रकाशित: (2013)

Almost goodbye
द्वारा: Mala Hayati Abdul Khir
प्रकाशित: (2014)

Simple, efficient, and neural algorithms for sparse coding
द्वारा: Arora, Sanjeev, और अन्य
प्रकाशित: (2018)

Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices
द्वारा: Moitra, Ankur
प्रकाशित: (2016)

Vertex Sparsification and Oblivious Reductions
द्वारा: Moitra, Ankur
प्रकाशित: (2014)

Nonnegative wealth, absence of arbitrage, and feasible consumption plans
द्वारा: Dybvig, Philip H., और अन्य
प्रकाशित: (2009)

An efficient sum of squares nonnegativity certificate for quaternary quartic
द्वारा: Pasechnik, D
प्रकाशित: (2015)

Minimax design of nonnegative finite impulse response filters
द्वारा: Lai, Xiaoping, और अन्य
प्रकाशित: (2014)

Almost sure convergence of the forward–backward–forward splitting algorithm
द्वारा: Vu, Bang Cong
प्रकाशित: (2017)

Clustering Mixtures with Almost Optimal Separation in Polynomial Time
द्वारा: Liu, Allen, और अन्य
प्रकाशित: (2022)