تقرير
A simple inverse power method for balanced graph cut
| العنوان: | A simple inverse power method for balanced graph cut |
|---|---|
| المؤلفون: | Shao, Sihong, Yang, Chuan |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Optimization and Control, Mathematics - Combinatorics, Mathematics - Numerical Analysis, Mathematics - 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 $\theta$-balanced cut which reduces to the balanced cut when $\theta=1$. When $\mathbf{SIP}$ reaches its local optimum, we seamlessly transfer to solve the $\theta$-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 $\theta$. 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. Comment: 24 pages, 10 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2405.18705 |
| رقم الأكسشن: | edsarx.2405.18705 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |