A simple inverse power method for balanced graph cut
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916264900820992 |
|---|---|
| author | Shao, Sihong Yang, Chuan |
| author_facet | Shao, Sihong Yang, Chuan |
| contents | The existing inverse power ($\mathbf{IP}$) method for solving the balanced graph cut lacks local convergence and its inner subproblem requires a nonsmooth convex solver. To address these issues, we develop a simple inverse power ($\mathbf{SIP}$) method using a novel equivalent continuous formulation of the balanced graph cut, and its inner subproblem allows an explicit analytic solution, which is the biggest advantage over $\mathbf{IP}$ and constitutes the main reason why we call it $\mathit{simple}$. By fully exploiting the closed-form of the inner subproblem solution, we design a boundary-detected subgradient selection with which $\mathbf{SIP}$ is proved to be locally converged. We show that $\mathbf{SIP}$ is also applicable to a new ternary valued $θ$-balanced cut which reduces to the balanced cut when $θ=1$. When $\mathbf{SIP}$ reaches its local optimum, we seamlessly transfer to solve the $θ$-balanced cut within exactly the same iteration algorithm framework and thus obtain $\mathbf{SIP}$-$\mathbf{perturb}$ -- an efficient local breakout improvement of $\mathbf{SIP}$, which transforms some ``partitioned" vertices back to the ``un-partitioned" ones through the adjustable $θ$. Numerical experiments on G-set for Cheeger cut and Sparsest cut demonstrate that $\mathbf{SIP}$ is significantly faster than $\mathbf{IP}$ while maintaining approximate solutions of comparable quality, and $\mathbf{SIP}$-$\mathbf{perturb}$ outperforms $\mathtt{Gurobi}$ in terms of both computational cost and solution quality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_18705 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A simple inverse power method for balanced graph cut Shao, Sihong Yang, Chuan Optimization and Control Numerical Analysis Combinatorics Spectral Theory 90C27, 05C50, 90C32, 35P30, 90C26 The existing inverse power ($\mathbf{IP}$) method for solving the balanced graph cut lacks local convergence and its inner subproblem requires a nonsmooth convex solver. To address these issues, we develop a simple inverse power ($\mathbf{SIP}$) method using a novel equivalent continuous formulation of the balanced graph cut, and its inner subproblem allows an explicit analytic solution, which is the biggest advantage over $\mathbf{IP}$ and constitutes the main reason why we call it $\mathit{simple}$. By fully exploiting the closed-form of the inner subproblem solution, we design a boundary-detected subgradient selection with which $\mathbf{SIP}$ is proved to be locally converged. We show that $\mathbf{SIP}$ is also applicable to a new ternary valued $θ$-balanced cut which reduces to the balanced cut when $θ=1$. When $\mathbf{SIP}$ reaches its local optimum, we seamlessly transfer to solve the $θ$-balanced cut within exactly the same iteration algorithm framework and thus obtain $\mathbf{SIP}$-$\mathbf{perturb}$ -- an efficient local breakout improvement of $\mathbf{SIP}$, which transforms some ``partitioned" vertices back to the ``un-partitioned" ones through the adjustable $θ$. Numerical experiments on G-set for Cheeger cut and Sparsest cut demonstrate that $\mathbf{SIP}$ is significantly faster than $\mathbf{IP}$ while maintaining approximate solutions of comparable quality, and $\mathbf{SIP}$-$\mathbf{perturb}$ outperforms $\mathtt{Gurobi}$ in terms of both computational cost and solution quality. |
| title | A simple inverse power method for balanced graph cut |
| topic | Optimization and Control Numerical Analysis Combinatorics Spectral Theory 90C27, 05C50, 90C32, 35P30, 90C26 |
| url | https://arxiv.org/abs/2405.18705 |