Maximum volume inscribed ellipsoid: A new simplex-structured matrix factorization framework via facet enumeration and convex optimization

Chia Hsiang Lin, Ruiyuan Wu, Wing Kin Ma, Chong Yung Chi, Yue Wang

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Consider a structured matrix factorization model where one factor is restricted to have its columns lying in the unit simplex. This simplex-structured matrix factorization (SSMF) model and the associated factorization techniques have spurred much interest in research topics over different areas, such as hyperspectral unmixing in remote sensing and topic discovery in machine learning, to name a few. In this paper we develop a new theoretical SSMF framework whose idea is to study a maximum volume ellipsoid inscribed in the convex hull of the data points. This maximum volume inscribed ellipsoid (MVIE) idea has not been attempted in prior literature, and we show a sufficient condition under which the MVIE framework guarantees exact recovery of the factors. The sufficient recovery condition we show for MVIE is much more relaxed than that of separable nonnegative matrix factorization (or pure-pixel search); coincidentally, it is also identical to that of minimum volume enclosing simplex, which is known to be a powerful SSMF framework for nonseparable problem instances. We also show that MVIE can be practically implemented by performing facet enumeration and then by solving a convex optimization problem. The potential of the MVIE framework is illustrated by numerical results.

Original languageEnglish
Pages (from-to)1651-1679
Number of pages29
JournalSIAM Journal on Imaging Sciences
Volume11
Issue number2
DOIs
Publication statusPublished - 2018 Jan 1

Fingerprint

Structured Matrices
Matrix Factorization
Convex optimization
Ellipsoid
Convex Optimization
Factorization
Facet
Enumeration
Recovery
Non-negative Matrix Factorization
Nonseparable
Learning systems
Framework
Remote sensing
Convex Hull
Remote Sensing
Pixels
Machine Learning
Pixel
Sufficient

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Applied Mathematics

Cite this

@article{cf144d56d62f4ec4ac32e496baae00a3,
title = "Maximum volume inscribed ellipsoid: A new simplex-structured matrix factorization framework via facet enumeration and convex optimization",
abstract = "Consider a structured matrix factorization model where one factor is restricted to have its columns lying in the unit simplex. This simplex-structured matrix factorization (SSMF) model and the associated factorization techniques have spurred much interest in research topics over different areas, such as hyperspectral unmixing in remote sensing and topic discovery in machine learning, to name a few. In this paper we develop a new theoretical SSMF framework whose idea is to study a maximum volume ellipsoid inscribed in the convex hull of the data points. This maximum volume inscribed ellipsoid (MVIE) idea has not been attempted in prior literature, and we show a sufficient condition under which the MVIE framework guarantees exact recovery of the factors. The sufficient recovery condition we show for MVIE is much more relaxed than that of separable nonnegative matrix factorization (or pure-pixel search); coincidentally, it is also identical to that of minimum volume enclosing simplex, which is known to be a powerful SSMF framework for nonseparable problem instances. We also show that MVIE can be practically implemented by performing facet enumeration and then by solving a convex optimization problem. The potential of the MVIE framework is illustrated by numerical results.",
author = "Lin, {Chia Hsiang} and Ruiyuan Wu and Ma, {Wing Kin} and Chi, {Chong Yung} and Yue Wang",
year = "2018",
month = "1",
day = "1",
doi = "10.1137/17M114145X",
language = "English",
volume = "11",
pages = "1651--1679",
journal = "SIAM Journal on Imaging Sciences",
issn = "1936-4954",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",

}

Maximum volume inscribed ellipsoid : A new simplex-structured matrix factorization framework via facet enumeration and convex optimization. / Lin, Chia Hsiang; Wu, Ruiyuan; Ma, Wing Kin; Chi, Chong Yung; Wang, Yue.

In: SIAM Journal on Imaging Sciences, Vol. 11, No. 2, 01.01.2018, p. 1651-1679.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Maximum volume inscribed ellipsoid

T2 - A new simplex-structured matrix factorization framework via facet enumeration and convex optimization

AU - Lin, Chia Hsiang

AU - Wu, Ruiyuan

AU - Ma, Wing Kin

AU - Chi, Chong Yung

AU - Wang, Yue

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Consider a structured matrix factorization model where one factor is restricted to have its columns lying in the unit simplex. This simplex-structured matrix factorization (SSMF) model and the associated factorization techniques have spurred much interest in research topics over different areas, such as hyperspectral unmixing in remote sensing and topic discovery in machine learning, to name a few. In this paper we develop a new theoretical SSMF framework whose idea is to study a maximum volume ellipsoid inscribed in the convex hull of the data points. This maximum volume inscribed ellipsoid (MVIE) idea has not been attempted in prior literature, and we show a sufficient condition under which the MVIE framework guarantees exact recovery of the factors. The sufficient recovery condition we show for MVIE is much more relaxed than that of separable nonnegative matrix factorization (or pure-pixel search); coincidentally, it is also identical to that of minimum volume enclosing simplex, which is known to be a powerful SSMF framework for nonseparable problem instances. We also show that MVIE can be practically implemented by performing facet enumeration and then by solving a convex optimization problem. The potential of the MVIE framework is illustrated by numerical results.

AB - Consider a structured matrix factorization model where one factor is restricted to have its columns lying in the unit simplex. This simplex-structured matrix factorization (SSMF) model and the associated factorization techniques have spurred much interest in research topics over different areas, such as hyperspectral unmixing in remote sensing and topic discovery in machine learning, to name a few. In this paper we develop a new theoretical SSMF framework whose idea is to study a maximum volume ellipsoid inscribed in the convex hull of the data points. This maximum volume inscribed ellipsoid (MVIE) idea has not been attempted in prior literature, and we show a sufficient condition under which the MVIE framework guarantees exact recovery of the factors. The sufficient recovery condition we show for MVIE is much more relaxed than that of separable nonnegative matrix factorization (or pure-pixel search); coincidentally, it is also identical to that of minimum volume enclosing simplex, which is known to be a powerful SSMF framework for nonseparable problem instances. We also show that MVIE can be practically implemented by performing facet enumeration and then by solving a convex optimization problem. The potential of the MVIE framework is illustrated by numerical results.

UR - http://www.scopus.com/inward/record.url?scp=85049255214&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049255214&partnerID=8YFLogxK

U2 - 10.1137/17M114145X

DO - 10.1137/17M114145X

M3 - Article

AN - SCOPUS:85049255214

VL - 11

SP - 1651

EP - 1679

JO - SIAM Journal on Imaging Sciences

JF - SIAM Journal on Imaging Sciences

SN - 1936-4954

IS - 2

ER -