Nonnegative matrix factorization (NMF) is a popular dimensionality reduction techniquebecause it is easily interpretable and can discern useful features. For a given matrixM (dimension n x m) whose entries are nonnegative and an integer r smaller than both n and m,NMF is the problem of finding nonnegative matrices A (dimension n x r) and W (dimension r x m) such thatM = AW. The matrix M could be noisy, in which case one seeks a robust algorithmthat solves M ≈ AW. The nonnegativity constraint in NMF has wide applicationsindata science problems like document clustering, facial feature extraction,hyperspectral unmixing etc.Geometrically, the rows of M can be viewed as a set of points in m-dimensional space. If we think ofthe rows of W as the vertices of an (unknown) W-simplex, then the data points lie in thisW-simplex. Therefore, NMF asks us to deduce the vertices of the simplex given the datapoints.NMF is a computationally hard problem though certain assumptions like separabilitylead to polynomial time algorithms. This assumes that all the vertices of theunknown simplex are already present as data points. In practice, this is not true in manysettings. Ge and Zou (2015) assumed subset separability which uses higher dimensionalstructures and gave a polynomial time algorithm to find the NMF robustly. In this thesis,we effectively replace one of their key algorithms that finds faces. We show a quadraticprogramming based approach which is efficient and can be employed in practice. Underbounded noise, our algorithm finds the faces of the simplex which contain enough datapoints, thus helping in finding the NMF.
【 预 览 】
附件列表
Files
Size
Format
View
A quadratic programming approach to find faces in robust nonnegative matrix factorization
PDF
download
878987797
028-85220240
