Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2304.05223 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929674397941760 |
|---|---|
| author | Huang, Xiaoqing Ang, Andersen Huang, Kun Zhang, Jie Wang, Yijie |
| author_facet | Huang, Xiaoqing Ang, Andersen Huang, Kun Zhang, Jie Wang, Yijie |
| contents | We study estimation of piecewise smooth signals over a graph. We propose a $\ell_{2,0}$-norm penalized Graph Trend Filtering (GTF) model to estimate piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness across the nodes. We prove that the proposed GTF model is simultaneously a k-means clustering on the signal over the nodes and a minimum graph cut on the edges of the graph, where the clustering and the cut share the same assignment matrix. We propose two methods to solve the proposed GTF model: a spectral decomposition method and a method based on simulated annealing. In the experiment on synthetic and real-world datasets, we show that the proposed GTF model has a better performances compared with existing approaches on the tasks of denoising, support recovery and semi-supervised classification. We also show that the proposed GTF model can be solved more efficiently than existing models for the dataset with a large edge set. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_05223 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Inhomogeneous graph trend filtering via a l2,0 cardinality penalty Huang, Xiaoqing Ang, Andersen Huang, Kun Zhang, Jie Wang, Yijie Machine Learning Social and Information Networks 65F50, 68U01, 68R01 G.1.6; G.1.10 We study estimation of piecewise smooth signals over a graph. We propose a $\ell_{2,0}$-norm penalized Graph Trend Filtering (GTF) model to estimate piecewise smooth graph signals that exhibit inhomogeneous levels of smoothness across the nodes. We prove that the proposed GTF model is simultaneously a k-means clustering on the signal over the nodes and a minimum graph cut on the edges of the graph, where the clustering and the cut share the same assignment matrix. We propose two methods to solve the proposed GTF model: a spectral decomposition method and a method based on simulated annealing. In the experiment on synthetic and real-world datasets, we show that the proposed GTF model has a better performances compared with existing approaches on the tasks of denoising, support recovery and semi-supervised classification. We also show that the proposed GTF model can be solved more efficiently than existing models for the dataset with a large edge set. |
| title | Inhomogeneous graph trend filtering via a l2,0 cardinality penalty |
| topic | Machine Learning Social and Information Networks 65F50, 68U01, 68R01 G.1.6; G.1.10 |
| url | https://arxiv.org/abs/2304.05223 |