As fuzzy c-means clustering (FCM) algorithm is sensitive to noise, local spatial information is often introduced to an objective function to improve the robustness of the FCM algorithm for image ...segmentation. However, the introduction of local spatial information often leads to a high computational complexity, arising out of an iterative calculation of the distance between pixels within local spatial neighbors and clustering centers. To address this issue, an improved FCM algorithm based on morphological reconstruction and membership filtering (FRFCM) that is significantly faster and more robust than FCM is proposed in this paper. First, the local spatial information of images is incorporated into FRFCM by introducing morphological reconstruction operation to guarantee noise-immunity and image detail-preservation. Second, the modification of membership partition, based on the distance between pixels within local spatial neighbors and clustering centers, is replaced by local membership filtering that depends only on the spatial neighbors of membership partition. Compared with state-of-the-art algorithms, the proposed FRFCM algorithm is simpler and significantly faster, since it is unnecessary to compute the distance between pixels within local spatial neighbors and clustering centers. In addition, it is efficient for noisy image segmentation because membership filtering are able to improve membership partition matrix efficiently. Experiments performed on synthetic and real-world images demonstrate that the proposed algorithm not only achieves better results, but also requires less time than the state-of-the-art algorithms for image segmentation.
Adversarial Manifold Estimation Aamari, Eddie; Knop, Alexander
Foundations of computational mathematics,
10/2022
Journal Article
Recenzirano
Odprti dostop
This paper studies the statistical query (SQ) complexity of estimating $d$-dimensional submanifolds in $\mathbb{R}^n$. We propose a purely geometric algorithm called Manifold Propagation, that ...reduces the problem to three natural geometric routines: projection, tangent space estimation, and point detection. We then provide constructions of these geometric routines in the SQ framework. Given an adversarial $\mathrm{STAT}(\tau)$ oracle and a target Hausdorff distance precision $\varepsilon = \Omega(\tau^{2 / (d + 1)})$, the resulting SQ manifold reconstruction algorithm has query complexity $O(n \operatorname{polylog}(n) \varepsilon^{-d / 2})$, which is proved to be nearly optimal. In the process, we establish low-rank matrix completion results for SQ's and lower bounds for randomized SQ estimators in general metric spaces.
Recently, multi-view clustering attracts much attention, which aims to take advantage of multi-view information to improve the performance of clustering. However, most recent work mainly focuses on ...the self-representation-based subspace clustering, which is of high computation complexity. In this paper, we focus on the Markov chain-based spectral clustering method and propose a novel essential tensor learning method to explore the high-order correlations for multi-view representation. We first construct a tensor based on multi-view transition probability matrices of the Markov chain. By incorporating the idea from the robust principle component analysis, tensor singular value decomposition (t-SVD)-based tensor nuclear norm is imposed to preserve the low-rank property of the essential tensor, which can well capture the principle information from multiple views. We also employ the tensor rotation operator for this task to better investigate the relationship among views as well as reduce the computation complexity. The proposed method can be efficiently optimized by the alternating direction method of multipliers (ADMM). Extensive experiments on seven real-world datasets corresponding to five different applications show that our method achieves superior performance over other state-of-the-art methods.
We propose a Monte Carlo algorithm to sample from high dimensional probability distributions that combines Markov chain Monte Carlo and importance sampling. We provide a careful theoretical analysis, ...including guarantees on robustness to high dimensionality, explicit comparison with standard Markov chain Monte Carlo methods and illustrations of the potential improvements in efficiency. Simple and concrete intuition is provided for when the novel scheme is expected to outperform standard schemes. When applied to Bayesian variable-selection problems, the novel algorithm is orders of magnitude more efficient than available alternative sampling schemes and enables fast and reliable fully Bayesian inferences with tens of thousand regressors.
Swarm robotics deals with the design, construction, and deployment of large groups of robots that coordinate and cooperatively solve a problem or perform a task. It takes inspiration from natural ...self-organizing systems, such as social insects, fish schools, or bird flocks, characterized by emergent collective behavior based on simple local interaction rules <xref ref-type="bibr" rid="ref1">1 , <xref ref-type="bibr" rid="ref2">2 . Typically, swarm robotics extracts engineering principles from the study of those natural systems in order to provide multirobot systems with comparable abilities. This way, it aims to build systems that are more robust, fault-tolerant, and flexible than single robots and that can better adapt their behavior to changes in the environment.
Evolutionary algorithms have been shown to be powerful for solving multiobjective optimization problems, in which nondominated sorting is a widely adopted technique in selection. This technique, ...however, can be computationally expensive, especially when the number of individuals in the population becomes large. This is mainly because in most existing nondominated sorting algorithms, a solution needs to be compared with all other solutions before it can be assigned to a front. In this paper we propose a novel, computationally efficient approach to nondominated sorting, termed efficient nondominated sort (ENS). In ENS, a solution to be assigned to a front needs to be compared only with those that have already been assigned to a front, thereby avoiding many unnecessary dominance comparisons. Based on this new approach, two nondominated sorting algorithms have been suggested. Both theoretical analysis and empirical results show that the ENS-based sorting algorithms are computationally more efficient than the state-of-the-art nondominated sorting methods.
We show that multigrid ideas can be used to reduce the computational complexity of estimating an expected value arising from a stochastic differential equation using Monte Carlo path simulations. In ...the simplest case of a Lipschitz payoff and a Euler discretisation, the computational cost to achieve an accuracy of O ( ) is reduced from O ( –3 ) to O ( –2 (log ) 2 ). The analysis is supported by numerical results showing significant computational savings.
KingdominoTM is a board game designed by Bruno Cathala and edited by Blue Orange since 2016. The goal is to place 2×1 dominoes on a grid layout, and get a better score than other players. Each 1×1 ...domino cell has a color that must match at least one adjacent cell, and an integer number of crowns (possibly none) used to compute the score. We prove that even with full knowledge of the future of the game, it is NP-complete to decide whether a given score is achievable at KingdominoTM.
Epilepsy, a brain disease generally associated with seizures, has tremendous effects on people’s quality of life. Diagnosis of epileptic seizures is commonly performed on electroencephalography (EEG) ...signals, and by using computer-aided diagnosis systems (CADS), neurologists can diagnose epileptic seizure stages more accurately. In these systems, a mandatory stage is feature extraction, performed by handcrafting features or learning them, ordinarily by a deep neural net. While researches in this field commonly show the value of a group of limited features, yet an accurate comparison between different suggested features is essential. In this article, first, a comparison between the importance of 50 different handcrafted features for seizure detection is presented. Additionally, the computational complexity of features is investigated as well. Then the best features based on Fisher scores are picked to classify signals on a benchmark dataset for evaluation. Additionally, a convolutional autoencoder with five layers is applied to learn features in order to have a complete comparison among feature extraction approaches. Finally, a hybrid method is employed, which combines handcrafted features and encoding of autoencoder to reach high performance in seizure detection in EEG signals.
•A comparison of fifty features of different types for seizure detection is presented.•Features are from time and frequency domain with non-linear ones.•Computational complexity of each feature is also presented.•Additionally, those features are compared to learned features by proposed CNN-AE.•Finally, employing a hybrid method from all features best results are obtained.
PDF
