University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Steve VavasisExport this event to calendar

Friday, November 23, 2007 — 3:30 PM to 4:30 PM EST

Greedy Algorithms and Complexity for Nonnegative Matrix Factorization

Speaker: Steve Vavasis
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Nonnegative Matrix Factorization (NMF) has emerged in the past decade as an important tool for information retrieval and clustering. NMF was originally considered as early as 1983 in the mathematical literature, but did not become popular for information retrieval until the work of Lee and Seung in 1999. It has been successfully applied to text and image databases, biochemical laboratory data, and even music. The most popular class of algorithms uses local improvement heuristics, but another class of algorithms based on greedy rank-one downdating has also shown a lot of promise. We describe our development of a greedy downdating algorithm and prove that it can successfully classify text databases in some restricted models of text. We also consider the complexity of the NMF problem, showing that it is NP-hard and relating it to a problem in polyhedral combinatorics.

Parts of this talk represent joint work with Michael Biggs (UWaterloo) and Ali Ghodsi (UWaterloo).

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2020 (92)
    1. November (1)
    2. October (1)
    3. September (12)
    4. August (11)
    5. July (17)
    6. June (11)
    7. May (6)
    8. March (11)
    9. February (11)
    10. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)