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

Statistical mechanics analysis of thresholding 1-bit compressed sensing

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第8期2016卷 083405-083405页

作者： Xu, Yingying Kabashima, Yoshiyuki Aalto Univ Sch Sci Dept Comp Sci POB 15400 FI-00076 Aalto Finland Tokyo Inst Technol Dept Math & Comp Sci Midori Ku G5-224259 Nagatsuda Chou Yokohama Kanagawa 2268502 Japan

The one-bit compressed sensing framework aims to reconstruct a sparse signal by only using the sign information of its linear measurements. To compensate for the loss of scale information, past studies in the area have proposed recovering the signal by imposing an additional constraint on the l(2)-norm of the signal. Recently, an alternative strategy that captures scale information by introducing a threshold parameter to the quantization process was advanced. In this paper, we analyze the typical behavior of thresholding 1-bit compressed sensing utilizing the replica method of statistical mechanics, so as to gain an insight for properly setting the threshold value. Our result shows that fixing the threshold at a constant value yields better performance than varying it randomly when the constant is optimally tuned, statistically. Unfortunately, the optimal threshold value depends on the statistical properties of the target signal, which may not be known in advance. In order to handle this inconvenience, we develop a heuristic that adaptively tunes the threshold parameter based on the frequency of positive ( or negative) values in the binary outputs. Numerical experiments show that the heuristic exhibits satisfactory performance while incurring low computational cost.

关键词： analysis of algorithms statistical inference cavity and replica method

来源：评论

学校读者我要写书评

暂无评论

analysis of false-reject probability in distance bounding protocols with mixed challenges over RFID noisy communication channel

引用

INFORMATION PROCESSING LETTERS 2015年第6-8期115卷 623-629页

作者： Jannati, Hoda Falahati, Abolfazl Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Iran Univ Sci & Technol Dept Elect Engn DCCS Lab Tehran Iran

To protect RFID systems against the relay attack, distance bounding protocols are proposed based upon the round trip time measurements of the executed messages. With such protocols, in addition to tags' authentication, the reader estimates an upper bound for the physical distance between the tag and itself. Recently, Kim and Avoine proposed two distance bounding protocols called KM and KA2 both utilize mixed random and predefined challenges. It is well-known that KA2 can provide a good performance in view of mafia fraud resistance and system memory requirements for the tags. Since RFID systems and distance bounding protocols are particularly susceptible to noise, in this paper, KM and KA2 are analyzed to compute the rejection probability of a valid tag due to channel errors. In this case, the analysis as well as simulation results shows that increasing the number of rounds (iterations) with predefined challenges causes the rejection probability of a valid tag to increase. (c) 2015 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Distance bounding protocol False-accept probability False-reject probability Relay attack

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of the (1+1) Evolutionary Algorithm for the Multiprocessor Scheduling Problem

引用

ALGORITHMICA 2015年第1期73卷 21-41页

作者： Zhou, Yuren Zhang, Jun Wang, Yong S China Univ Technol Sch Comp Sci & Engn Guangzhou 510006 Guangdong Peoples R China Sun Yat Sen Univ Dept Comp Sci Guangzhou 510275 Guangdong Peoples R China Cent S Univ Coll Informat Sci & Engn Changsha Hunan Peoples R China

In recent years, there has been considerable progress in the theoretical study of evolutionary algorithms (EAs) for discrete optimization problems. However, results on the performance analysis of EAs for NP-hard problems are rare. This paper contributes a theoretical understanding of EAs on the NP-hard multiprocessor scheduling problem. The worst-case bound on the (1+1)EA for the multiprocessor scheduling problem and a worst-case example are presented. It is proved that the (1+1)EA on problem achieves an approximation ratio of in expected time . Finally, the theoretical analysis on three selected instances of the multiprocessor scheduling problem shows that EAs outperform local search algorithms on these instances.

关键词： Evolutionary algorithms Scheduling problem Local search algorithms Approximation algorithms analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Typical performance of approximation algorithms for NP-hard problems

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第11期2016卷 113401-113401页

作者： Takabe, Satoshi Hukushima, Koji Univ Tokyo Grad Sch Arts & Sci Meguro Ku 3-8-1 Komaba Tokyo 1538902 Japan Natl Inst Mat Sci Ctr Mat Res Informat Integrat 1-2-1 Sengen Tsukuba Ibaraki 3050047 Japan

Typical performance of approximation algorithms is studied for randomized minimum vertex cover problems. A wide class of random graph ensembles characterized by an arbitrary degree distribution is discussed with the presentation of a theoretical framework. Herein, three approximation algorithms are examined: linear-programming relaxation, loopy-belief propagation, and the leaf-removal algorithm. The former two algorithms are analyzed using a statistical-mechanical technique, whereas the average-case analysis of the last one is conducted using the generating function method. These algorithms have a threshold in the typical performance with increasing average degree of the random graph, below which they find true optimal solutions with high probability. Our study reveals that there exist only three cases, determined by the order of the typical performance thresholds. In addition, we provide some conditions for classification of the graph ensembles and demonstrate explicitly some examples for the difference in thresholds.

关键词： analysis of algorithms Optimization over networks Cavity and replica method Typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

A divisive spectral method for network community detection

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第3期2016卷 033403-033403页

作者： Cheng, Jianjun Li, Longjie Leng, Mingwei Lu, Weiguo Yao, Yukai Chen, Xiaoyun Lanzhou Univ Sch Informat Sci & Engn Lanzhou 730000 Gansu Peoples R China Shangrao Normal Univ Sch Math & Comp Sci Xinzhou Jiangxi Peoples R China Lanzhou Univ Int Off Lanzhou 730000 Gansu Peoples R China

Community detection is a fundamental problem in the domain of complex network analysis. It has received great attention, and many community detection methods have been proposed in the last decade. In this paper, we propose a divisive spectral method for identifying community structures from networks which utilizes a sparsification operation to pre-process the networks first, and then uses a repeated bisection spectral algorithm to partition the networks into communities. The sparsification operation makes the community boundaries clearer and sharper, so that the repeated spectral bisection algorithm extract high-quality community structures accurately from the sparsified networks. Experiments show that the combination of network sparsification and a spectral bisection algorithm is highly successful, the proposed method is more effective in detecting community structures from networks than the others.

关键词： data mining (theory) analysis of algorithms network dynamics clustering techniques

来源：评论

学校读者我要写书评

暂无评论

Improving Width-3 Joint Sparse Form to Attain Asymptotically Optimal Complexity on Average Case

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1216-1222页

作者： Imai, Hiroshi Suppakitpaisarn, Vorapong Univ Tokyo Grad Sch Informat Sci & Technol Tokyo 1130033 Japan Natl Inst Informat Global Res Ctr Big Data Math Tokyo 1018430 Japan JST ERATO Kawarabayashi Large Graph Project Tokyo 1018430 Japan

In this paper, we improve a width-3 joint sparse form proposed by Okeya, Katoh, and Nogami. After the improvement, the representation can attain an asymtotically optimal complexity found in our previous work. Although claimed as optimal by the authors, the average computation time of multi-scalar multiplication obtained by the representation is 563/1574n + o(n) approximate to 0.3577n + o(n). That number is larger than the optimal complexity 281/786n + o(n) approximate to 0.3575n + o(n) found in our previous work. To optimize the width-3 joint sparse form, we add more cases to the representation. After the addition, we can show that the complexity is updated to 281/786n + o(n) approximate to 0.3575n + o(n), which implies that the modified representation is asymptotically optimal. Compared to our optimal algorithm in the previous work, the modified width-3 joint sparse form uses less dynamic memory, but it consumes more static memory.

关键词： analysis of algorithms number representation elliptic curve cryptography multi-scalar multiplication width-3 joint sparse form

来源：评论

学校读者我要写书评

暂无评论

Typical reconstruction performance for distributed compressed sensing based on l_2,1-norm regularized least square and Bayesian optimal reconstruction: influences of noise

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第6期2016卷 063304-063304页

作者： Shiraki, Yoshifumi Kabashima, Yoshiyuki NTT Corp NTT Commun Sci Labs Atsugi Kanagawa 2430198 Japan Tokyo Inst Technol Dept Math & Comp Sci Yokohama Kanagawa 2268502 Japan

A signal model called joint sparse model 2 (JSM-2) or the multiple measurement vector problem, in which all sparse signals share their support, is important for dealing with practical signal processing problems. In this paper, we investigate the typical reconstruction performance of noisy measurement JSM-2 problems for l(2,1)-norm regularized least square reconstruction and the Bayesian optimal reconstruction scheme in terms of mean square error. Employing the replica method, we show that these schemes, which exploit the knowledge of the sharing of the signal support, can recover the signals more precisely as the number of channels increases. In addition, we compare the reconstruction performance of two different ensembles of observation matrices: one is composed of independent and identically distributed random Gaussian entries and the other is designed so that row vectors are orthogonal to one another. As reported for the single-channel case in earlier studies, our analysis indicates that the latter ensemble offers better performance than the former ones for the noisy JSM-2 problem. The results of numerical experiments with a computationally feasible approximation algorithm we developed for this study agree with the theoretical estimation.

关键词： analysis of algorithms message-passing algorithms source and channel coding

来源：评论

学校读者我要写书评

暂无评论

Localized eigenvectors of the non-backtracking matrix

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第2期000卷 023404-023404页

作者： Kawamoto, Tatsuro Tokyo Inst Technol Dept Computat Intelligence & Syst Sci Midori Ku 4259-G5-22 Nagatsuta Cho Yokohama Kanagawa 2268502 Japan

In the case of graph partitioning, the emergence of localized eigenvectors can cause the standard spectral method to fail. To overcome this problem, the spectral method using a non-backtracking matrix was proposed. Based on numerical experiments on several examples of real networks, it is clear that the non-backtracking matrix does not exhibit localization of eigenvectors. However, we show that localized eigenvectors of the non-backtracking matrix can exist outside the spectral band, which may lead to deterioration in the performance of graph partitioning.

关键词： analysis of algorithms exact results clustering techniques

来源：评论

学校读者我要写书评

暂无评论

Finding network communities using modularity density

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2016年第12期2016卷 123402-123402页

作者： Botta, Federico del Genio, Charo I. Univ Warwick Ctr Complex Sci Coventry CV4 7AL W Midlands England Univ Warwick Sch Life Sci Coventry CV4 7AL W Midlands England

Many real-world complex networks exhibit a community structure, in which the modules correspond to actual functional units. Identifying these communities is a key challenge for scientists. A common approach is to search for the network partition that maximizes a quality function. Here, we present a detailed analysis of a recently proposed function, namely modularity density. We show that it does not incur in the drawbacks su. ered by traditional modularity, and that it can identify networks without ground-truth community structure, deriving its analytical dependence on link density in generic random graphs. In addition, we show that modularity density allows an easy comparison between networks of di. erent sizes, and we also present some limitations that methods based on modularity density may su. er from. Finally, we introduce an e. cient, quadratic community detection algorithm based on modularity density maximization, validating its accuracy against theoretical predictions and on a set of benchmark networks.

关键词： Random graphs networks analysis of algorithms Heuristics algorithms Typical-case computational complexity

来源：评论

学校读者我要写书评

暂无评论

Maximum likelihood analysis of algorithms and data structures

引用

THEORETICAL COMPUTER SCIENCE 2010年第1期411卷 188-212页

作者： Laube, Ulrich Nebel, Markus E. Tech Univ Kaiserslautern Fachbereich Informat D-67663 Kaiserslautern Germany

We present a new approach for an average-case analysis of algorithms and data structures that supports a non-uniform distribution of the inputs and is based on the maximum likelihood training of stochastic grammars. The approach is exemplified by an analysis of the expected size of binary tries as well as by three sorting algorithms and it is compared to the known results that were obtained by traditional techniques. Investigating traditional settings like the random permutation model, we rediscover well-known results formerly derived by pure analytic methods;changing to biased data yields original results. All but one step of our analysis can be automated on top of a computer-algebra system. Thus Our new approach can reduce the effort required for an average-case analysis, allowing for the consideration of realistic input distributions with unknown distribution functions at the same time. As a by-product, our approach yields an easy way to generate random combinatorial objects according to various probability distributions. (C) 2009 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Stochastic context free grammars Generating functions Maximum likelihood method Tries Sorting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：