A compressed sensing based least squares approach to semi-supervised local cluster extraction

DOI10.1007/S10915-022-02052-XarXiv2202.02904OpenAlexW4318771067MaRDI QIDQ6158985FDOQ6158985

Ming-Jun Lai, Zhaiming Shen

Publication date: 20 June 2023

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: A least squares semi-supervised local clustering algorithm based on the idea of compressed sensing is proposed to extract clusters from a graph with known adjacency matrix. The algorithm is based on a two-stage approach similar to the one in cite{LaiMckenzie2020}. However, under a weaker assumption and with less computational complexity than the one in cite{LaiMckenzie2020}, the algorithm is shown to be able to find a desired cluster with high probability. The ``one cluster at a time" feature of our method distinguishes it from other global clustering methods. Several numerical experiments are conducted on the synthetic data such as stochastic block model and real data such as MNIST, political blogs network, AT&T and YaleB human faces data sets to demonstrate the effectiveness and efficiency of our algorithm.

Full work available at URL: https://arxiv.org/abs/2202.02904

zbMATH Keywords

graph clusteringleast squarescompressed sensinggraph Laplaciansemi-supervised clusteringlocal clustering

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A proof of the block model threshold conjecture
• Empirical Analysis of an Evolving Social Network
• Title not available (Why is that?)
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Title not available (Why is that?)
• Subspace Pursuit for Compressive Sensing Signal Reconstruction
• Linear Inversion of Band-Limited Reflection Seismograms
• Community Detection and Stochastic Block Models
• Using PageRank to Locally Partition a Graph
• Auction dynamics: a volume constrained MBO scheme
• An effective region force for some variational models for learning and clustering
• Title not available (Why is that?)
• Graph-based Natural Language Processing and Information Retrieval
• Compressive Sensing for Cut Improvement and Local Clustering
• Title not available (Why is that?)

Cited In (1)

• K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance

This page was built for publication: A compressed sensing based least squares approach to semi-supervised local cluster extraction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6158985)