國立虎尾科技大學 |

Fast Spectral and Convex Methods in Clustering.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Fast Spectral and Convex Methods in Clustering./
Author:	Xie, Kaiying.
Description:	1 online resource (104 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 85-04, Section: B.
Contained By:	Dissertations Abstracts International85-04B.
Subject:	Electrical engineering. -
Online resource:	click for full text (PQDT)
ISBN:	9798380595889

Fast Spectral and Convex Methods in Clustering.
Xie, Kaiying.

Fast Spectral and Convex Methods in Clustering. - 1 online resource (104 pages)

Source: Dissertations Abstracts International, Volume: 85-04, Section: B.

Thesis (Ph.D.)--The Ohio State University, 2023.

Includes bibliographical references

Many clustering problems are combinatorial optimization problems, which are hard to solve directly. In this dissertation, we consider relaxing these clustering problems to convex semidefinite problems and to an optimization problem that can be solved by spectral method.First, we address the minimum bisection problem under the stochastic block model. Previous studies show that the planted partition can be recovered exactly using a semidefinite program when there is enough signal, i.e., when the similarity within clusters is sufficiently larger than the separation between different clusters. However, semidefinite programs are slow in practice. We introduce a sketch-and-solve approach to accelerate this process. We show that when there is more signal, we can sketch to a smaller problem, and thus the planted partition can be recovered in a shorter amount of time.Next, we extend this sketch-and-solve idea to the Peng-Wei semidefinite program to solve the k-means clustering problem. Similar to the minimum bisection problem, our approach recovers the optimal partition faster when there is more signal. Meanwhile, for general data, we develop a sketch-and-solve approach to provide a high-confidence lower bound on the optimal k-means value. Experiments show that for some real-world datasets, our lower bound provides a good posteriori certificate for the clustering result obtained by k-means++.Finally, we provide a spectral method to compute a lower bound on the optimal k- means value. This spectral lower bound can be computed as fast as one singular value decomposition. Theoretical analysis and numerical results show that our lower bound has good performance for high-dimensional data.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2024

Mode of access: World Wide Web

ISBN: 9798380595889Subjects--Topical Terms:

596380
Electrical engineering.
Subjects--Index Terms:

Convex methodsIndex Terms--Genre/Form:

554714
Electronic books.

Fast Spectral and Convex Methods in Clustering.
LDR:03134ntm a22004097 4500 001 1143683
005 20240517104629.5
006 m o d
007 cr mn ---uuuuu
008 250605s2023 xx obm 000 0 eng d
020 $a 9798380595889
035 $a (MiAaPQ)AAI30788321
035 $a (MiAaPQ)OhioLINKosu1688997858249613
035 $a AAI30788321
040 $a MiAaPQ $b eng $c MiAaPQ $d NTU
100 1 $a Xie, Kaiying. $3 1468452
245 1 0 $a Fast Spectral and Convex Methods in Clustering.
264 0 $c 2023
300 $a 1 online resource (104 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 85-04, Section: B.
500 $a Advisor: Mixon, Dustin;Potter, Lee.
502 $a Thesis (Ph.D.)--The Ohio State University, 2023.
504 $a Includes bibliographical references
520 $a Many clustering problems are combinatorial optimization problems, which are hard to solve directly. In this dissertation, we consider relaxing these clustering problems to convex semidefinite problems and to an optimization problem that can be solved by spectral method.First, we address the minimum bisection problem under the stochastic block model. Previous studies show that the planted partition can be recovered exactly using a semidefinite program when there is enough signal, i.e., when the similarity within clusters is sufficiently larger than the separation between different clusters. However, semidefinite programs are slow in practice. We introduce a sketch-and-solve approach to accelerate this process. We show that when there is more signal, we can sketch to a smaller problem, and thus the planted partition can be recovered in a shorter amount of time.Next, we extend this sketch-and-solve idea to the Peng-Wei semidefinite program to solve the k-means clustering problem. Similar to the minimum bisection problem, our approach recovers the optimal partition faster when there is more signal. Meanwhile, for general data, we develop a sketch-and-solve approach to provide a high-confidence lower bound on the optimal k-means value. Experiments show that for some real-world datasets, our lower bound provides a good posteriori certificate for the clustering result obtained by k-means++.Finally, we provide a spectral method to compute a lower bound on the optimal k- means value. This spectral lower bound can be computed as fast as one singular value decomposition. Theoretical analysis and numerical results show that our lower bound has good performance for high-dimensional data.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2024
538 $a Mode of access: World Wide Web
650 4 $a Electrical engineering. $3 596380
650 4 $a Computer engineering. $3 569006
650 4 $a Applied mathematics. $3 1069907
653 $a Convex methods
653 $a Clustering
653 $a Combinatorial optimization
653 $a Stochastic block model
653 $a Singular value decomposition
655 7 $a Electronic books. $2 local $3 554714
690 $a 0544
690 $a 0464
690 $a 0364
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a The Ohio State University. $b Electrical and Computer Engineering. $3 845530
773 0 $t Dissertations Abstracts International $g 85-04B.
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=30788321 $z click for full text (PQDT)