检索结果-内蒙古大学图书馆

16th IEEE International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP)

作者： Zhou, Qiang Cai, Shi-Min Zhang, Yi-Cheng Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Univ Elect Sci & Technol China Inst Fundamental & Frontier Sci Chengdu 611731 Peoples R China Univ Fribourg Dept Phys CH-1700 Fribourg Switzerland

ISBN: (纸本)9781728142425

Compared with stochastic networks, the distribution of node degrees in real-world networks is characterized by heterogeneity. spectral strategies based on the matrix eigenvector have been widely applied in the analysis of this type of network data, particularly for spatial division and community detection. Considering the performance of normalized Laplace matrix in heterogeneous networks outperforms some other common matrices, herein, a spectral strategy based on the eigenvector of matrix is proposed to tackle the modularity maximization problem in community detection.

关键词： Community diction Heterogeneous networks Normalized Laplace matrix spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved analysis of spectral algorithm for clustering

引用

OPTIMIZATION LETTERS 2021年第4期15卷 1303-1325页

作者： Mizutani, Tomohiko Shizuoka Univ Dept Math & Syst Engn Naka Ku 3-5-1 Johoku Hamamatsu Shizuoka 4328561 Japan

spectral algorithms are graph partitioning algorithms that partition a node set of a graph into groups by using a spectral embedding map. Clustering techniques based on the algorithms are referred to as spectral clustering and are widely used in data analysis. To gain a better understanding of why spectral clustering is successful, Peng et al. (In: Proceedings of the 28th conference on learning theory (COLT), vol 40, pp 1423-1455, 2015) and Kolev and Mehlhorn (In: 24th annual European symposium on algorithms (ESA 2016), vol 57, pp 57:1-57:14, 2016) studied the behavior of a certain type of spectral algorithm for a class of graphs, called well-clustered graphs. Specifically, they put an assumption on graphs and showed the performance guarantee of the spectral algorithm under it. The algorithm they studied used the spectral embedding map developed by Shi and Malik (IEEE Trans Pattern Anal Mach Intell 22(8):888-905, 2000). In this paper, we improve on their results, giving a better performance guarantee under a weaker assumption. We also evaluate the performance of the spectral algorithm with the spectral embedding map developed by Ng et al. (In: Advances in neural information processing systems 14 (NIPS), pp 849-856, 2001).

关键词： spectral algorithm Clustering Graph partitioning Performance guarantee

来源：评论

学校读者我要写书评

暂无评论

Exact recovery in the hypergraph stochastic block model: A spectral algorithm

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2020年第0期593卷 45-73页

作者： Cole, Sam Zhu, Yizhe Univ Manitoba Dept Math Winnipeg MB R3T 2MB Canada Univ Calif San Diego Dept Math La Jolla CA 92093 USA

We consider the exact recovery problem in the hypergraph stochastic block model (HSBM) with k blocks of equal size. More precisely, we consider a random d-uniform hypergraph H with n vertices partitioned into k clusters of size s = n/k. Hyperedges e are added independently with probability p if e is contained within a single cluster and q otherwise, where 0 <= q < p <= 1. We present a spectral algorithm which recovers the clusters exactly with high probability, given mild conditions on n, k, p, q, and d. Our algorithm is based on the adjacency matrix of H, which is a symmetric nxn matrix whose (u, v)-th entry is the number of hyperedges containing both u and v. To the best of our knowledge, our algorithm is the first to guarantee exact recovery when the number of clusters k = circle minus(root n). (C) 2020 Elsevier Inc. All rights reserved.

关键词： Random hypergraph Stochastic block model Community detection spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

A spectral algorithm for Inference in Hidden semi-Markov Models

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2017年第1期18卷 1164-1202页

作者： Melnyk, Igor Banerjee, Arindam IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55414 USA

Hidden semi-Markov models (HSMMs) are latent variable models which allow latent state persistence and can be viewed as a generalization of the popular hidden Markov models (HMMs). In this paper, we introduce a novel spectral algorithm to perform inference in HSMMs. Unlike expectation maximization (EM), our approach correctly estimates the probability of given observation sequence based on a set of training sequences. Our approach is based on estimating moments from the sample, whose number of dimensions depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few matrix inversions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the advantage of the algorithm over EM in terms of speed and accuracy, especially for large data sets.

关键词： Graphical models hidden semi-Markov model spectral algorithm tensor analysis aviation safety

来源：评论

学校读者我要写书评

暂无评论

A spectral algorithm for learning Hidden Markov Models

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第5期78卷 1460-1480页

作者： Hsu, Daniel Kakade, Sham M. Zhang, Tong Rutgers State Univ Piscataway NJ 08854 USA Univ Penn Philadelphia PA 19104 USA

Hidden Markov Models (HMMs) are one of the most fundamental and widely used statistical tools for modeling discrete time series. In general, learning HMMs from data is computationally hard (under cryptographic assumptions), and practitioners typically resort to search heuristics which suffer from the usual local optima issues. We prove that under a natural separation condition (bounds on the smallest singular value of the HMM parameters). there is an efficient and provably correct algorithm for learning HMMs. The sample complexity of the algorithm does not explicitly depend on the number of distinct (discrete) observations it implicitly depends on this quantity through spectral properties of the underlying HMM. This makes the algorithm particularly applicable to settings with a large number of observations, such as those in natural language processing where the space of observation is sometimes the words in a language. The algorithm is also simple, employing only a singular value decomposition and matrix multiplications. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Hidden Markov Models Latent variable models Observable operator models Time series spectral algorithm Singular value decomposition Learning probability distributions Unsupervised learning

来源：评论

学校读者我要写书评

暂无评论

A Fast spectral algorithm for Mean Estimation with Sub-Gaussian Rates 33

A Fast Spectral Algorithm for Mean Estimation with Sub-Gauss...

引用

33rd Conference on Learning Theory (COLT)

作者： Lei, Zhixian Luh, Kyle Venkat, Prayaag Zhang, Fred Harvard Univ Cambridge MA 02138 USA Univ Calif Berkeley Berkeley CA USA

We study the algorithmic problem of estimating the mean of a heavy-tailed random vector in R-d, given n i.i.d. samples. The goal is to design an efficient estimator that attains the optimal subgaussian error bound, only assuming that the random vector has bounded mean and covariance. Polynomial-time solutions to this problem are known but have high runtime due to their use of semidefinite programming (SDP). Moreover, conceptually, it remains open whether convex relaxation is truly necessary for this problem. In this work, we show that it is possible to go beyond SDP and achieve better computational efficiency. In particular, we provide a spectral algorithm that achieves the optimal statistical performance and runs in time (O) over tilde (n(2)d), improving upon the previous fastest runtime (O) over tilde (n(3.5) + n(2)d) by Cherapanamjeri et al. (COLT '19). Our algorithm is spectral in that it only requires (approximate) eigenvector computations, which can be implemented very efficiently by, for example, power iteration or the Lanczos method. At the core of our algorithm is a novel connection between the furthest hyperplane problem introduced by Karnin et al. (COLT '12) and a structural lemma on heavy-tailed distributions by Lugosi and Mendelson (Ann. Stat. '19). This allows us to iteratively reduce the estimation error at a geometric rate using only the information derived from the top singular vector of the data matrix, leading to a significantly faster running time.

关键词： High-dimensional statistics mean estimation robust statistics spectral algorithm

来源：评论

学校读者我要写书评

暂无评论

Adaptive spectral processing algorithm for staggered signals in weather radars

引用

IET RADAR SONAR AND NAVIGATION 2020年第11期14卷 1659-1670页

作者： Collado Rosell, Arturo Pascual, Juan Pablo Areta, Javier Univ Nacl Cuyo Instutito Balseiro Av Bustillo RA-9500 San Carlos De Bariloche Argentina CNEA GAIyANN GDTyPE LIATDept Ingn Telecomunicac Av Bustillo RA-9500 San Carlos De Bariloche Argentina Consejo Nacl Invest Cient & Tecn Consejo Nacl Invest Cient & Tecn Buenos Aires DF Argentina Univ Nacl Rio Negro RA-1463 Anasagasti Sc Bariloche Argentina

A spectral algorithm for processing staggered-pulse repetition time (SPRT) signals in weather radar is introduced. It includes new approaches for ground clutter filter and hydrometeor spectral moments estimation. The algorithm uses ideas similar to GMAP but applied to non-uniform sampled signals. This work is focused on staggered sequences 2/3, but can be extended to other staggered sequences. Monte Carlo experiments were used to evaluate the performance of the spectral moments estimators for simulated weather signal, in scenarios with and without the presence of ground clutter. When clutter is present, a study using different clutter-to-signal ratios was carried out, showing that the method can deal with a wide range of situations and is appropriate for implementation in real scenarios. A comparison against GMAP-TD was performed, showing similar estimation results for both algorithms and a fivefold processing speed improvement for the proposed method. The performance was also validated using real weather data RMA-12 from a radar located in San Carlos de Bariloche, Argentina. The proposed algorithm has an easy implementation and is a good candidate for real-time implementations.

关键词： signal sampling meteorological radar Monte Carlo methods geophysical signal processing radar signal processing radar clutter Doppler radar atmospheric techniques GMAP-TD similar estimation results fivefold processing speed improvement weather data RMA-12 real-time implementations adaptive spectral processing algorithm staggered signals weather radar spectral algorithm staggered-pulse repetition time signals ground clutter filter hydrometeor spectral moments estimation nonuniform sampled signals staggered sequences Monte Carlo experiments spectral moments estimators simulated weather signal clutter-to-signal ratios

来源：评论

学校读者我要写书评

暂无评论

A spectral algorithm for inference in hidden semi-Markov models

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2017年第1期18卷

作者： Igor Melnyk Arindam Banerjee IBM T. J. Watson Research Center Yorktown Heights NY Department of Computer Science and Engineering University of Minnesota Minneapolis MN

关键词： aviation safety graphical models hidden semi-Markov model spectral algorithm tensor analysis

来源：评论

学校读者我要写书评

暂无评论

Means of Hitting Times for Random Walks on Graphs: Connections, Computation, and Optimization

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2025年第2期19卷 1-35页

作者： Xia, Haisong Xu, Wanyue Zhang, Zuobai Zhang, Zhongzhi Fudan Univ Sch Comp Sci Shanghai Key Lab Intelligent Informat Proc Shanghai Peoples R China Fudan Univ Shanghai Engn Res Inst Blockchains Shanghai Peoples R China Fudan Univ Res Inst Intelligent Complex Syst Shanghai Peoples R China

For random walks on graph G with n vertices and m edges, the mean hitting time H-j from a vertex chosen from the stationary distribution to vertex j measures the importance for j, while the Kemeny constant K is the mean hitting time from one vertex to another selected randomly according to the stationary distribution. In this article, we first establish a connection between the two quantities, representing K in terms of H-j for all vertices. We then develop an efficient algorithm estimating H-j for all vertices and K in nearly linear time of m. Moreover, we extend the centrality H-j of a single vertex to H(S) of a vertex set S, and establish a link between H(S) and some other quantities. We further study the NP-hard problem of selecting a group S of k << n vertices with minimum H(S), whose objective function is monotonic and supermodular. We finally propose two greedy algorithms approximately solving the problem. The former has an approximation factor (1-k/k-1 1/e) and O(kn(3)) running time, while the latter returns a (1-k/k-1 1/e-& varepsilon;)-approximation solution in nearly-linear time of m, for any parameter 0<& varepsilon;<1. Extensive experiment results validate the performance of our algorithms.

关键词： Random walk hitting time Kemeny constant spectral algorithm complex network optimization vertex centrality

来源：评论

学校读者我要写书评

暂无评论

Learning theory of distributed spectral algorithms

引用

INVERSE PROBLEMS 2017年第7期33卷 074009-074009页

作者： Guo, Zheng-Chu Lin, Shao-Bo Zhou, Ding-Xuan Zhejiang Univ Sch Math Sci Hangzhou 310027 Zhejiang Peoples R China City Univ Hong Kong Dept Math Kowloon Hong Kong Peoples R China

spectral algorithms have been widely used and studied in learning theory and inverse problems. This paper is concerned with distributed spectral algorithms, for handling big data, based on a divide-and-conquer approach. We present a learning theory for these distributed kernel-based learning algorithms in a regression framework including nice error bounds and optimal minimax learning rates achieved by means of a novel integral operator approach and a second order decomposition of inverse operators. Our quantitative estimates are given in terms of regularity of the regression function, effective dimension of the reproducing kernel Hilbert space, and qualification of the filter function of the spectral algorithm. They do not need any eigenfunction or noise conditions and are better than the existing results even for the classical family of spectral algorithms.

关键词： distributed learning spectral algorithm integral operator learning rate

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：