Learning strictly orthogonal p-order nonnegative Laplacian embedding via smoothed iterative reweighted method

Laplacian embedding is a powerful graph based method with its ability in spectral clustering to reveal the intrinsic geometry of data in the high dimensional space. Imposing the orthogonality and the nonnegativity constraints can avoid degenerate and negative solutions, respectively. These two attributes are critical yet challenging to achieve simultaneously. Although, in recent years, many attempts have been made to overcome this, this problem is still not perfectly handled. We propose an effective algorithm to solve the Laplacian embedding problem that satisfies the both constraints. To promote the robustness of our embedding model against outliers, we exploit the p-order of the l2-norm distances to find the best solution of the spectral embedding from the input graph. Optimization with both orthonormal and nonnegative constraints is highly nonlinear and nonconvex in feasible domain. The p-order term in our objective further makes it nonsmooth and difficult to efficiently solve in general. We introduce a novel smoothed iterative reweighted method with a smoothness term to tackle this challenging optimization problem and rigorously analyze its convergence. We demonstrate the effectiveness and potential of our proposed method by extensive empirical studies on both synthetic and real data sets.

Name thesis:degree_name

Master of Science (M.S.)

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Colorado School of Mines. Arthur Lakes Library

Year dc:date.issued

2019

Author dc:creator

• Yang, Haoxuan

Advisor dc:contributor.advisor

• Wang, Hua

Committee members dc:contributor.committeemember

• Mehta, Dinesh P.
• Yang, Dejun

• data embedding
• Laplacian embedding
• optimization
• data mining
• clustering
• machine learning

Statement dc:rights

• Copyright of the original work is retained by the author.

Language dc:language.iso

eng, English

Identifier

T 8742

OAI identifier oai:identifier

oai:repository.mines.edu:11124/173087