English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Fast Newton-type Methods for the Least Squares Nonnegative Matrix Approximation Problem

Kim, D., Sra, S., & Dhillon, I. (2007). Fast Newton-type Methods for the Least Squares Nonnegative Matrix Approximation Problem. In C. Apte, D. Skillicorn, B. Liu, & S. Parthasarathy (Eds.), 2007 SIAM International Conference on Data Mining (pp. 343-354). Pittsburgh, PA, USA: Society for Industrial and Applied Mathematics.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0013-CE1F-F Version Permalink: https://hdl.handle.net/21.11116/0000-0003-E326-2
Genre: Conference Paper

Files

show Files

Locators

show
hide
Locator:
https://epubs.siam.org/doi/10.1137/1.9781611972771.31 (Publisher version)
Description:
-
OA-Status:

Creators

show
hide
 Creators:
Kim, D, Author
Sra, S1, Author           
Dhillon, I, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Nonnegative Matrix Approximation is an effective matrix decomposition technique that has proven to be useful for a wide variety of applications ranging from document analysis and image processing to bioinformatics. There exist a few algorithms for nonnegative matrix approximation (NNMA), for example, Lee & Seung's multiplicative updates, alternating least squares, and certain gradient descent based procedures. All of these procedures suffer from either slow convergence, numerical instabilities, or at worst, theoretical un-soundness. In this paper we present new and improved algorithms for the least-squares NNMA problem, which are not only theoretically well-founded, but also overcome many of the deficiencies of other methods. In particular, we use non-diagonal gradient scaling to obtain rapid convergence. Our methods provide numerical results superior to both Lee & Seung's method as well to the alternating least squares (ALS) heuristic, which is known to work well in some situations but has no theoretical guarantees (Berry et al. 2006). Our approach extends naturally to include regularization and box-constraints, without sacrificing convergence guarantees. We present experimental results on both synthetic and real-world datasets to demonstrate the superiority of our methods, in terms of better approximations as well as efficiency.

Details

show
hide
Language(s):
 Dates: 2007-04
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: 5219
DOI: 10.1137/1.9781611972771.31
 Degree: -

Event

show
hide
Title: Seventh SIAM International Conference on Data Mining (SDM 2007)
Place of Event: Minneapolis, MN, USA
Start-/End Date: 2007-04-26 - 2007-04-28

Legal Case

show

Project information

show

Source 1

show
hide
Title: 2007 SIAM International Conference on Data Mining
Source Genre: Proceedings
 Creator(s):
Apte, C, Editor
Skillicorn, D, Editor
Liu, B, Editor
Parthasarathy, S, Editor
Affiliations:
-
Publ. Info: Pittsburgh, PA, USA : Society for Industrial and Applied Mathematics
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 343 - 354 Identifier: ISBN: 978-0-898716-30-6