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

Dimension, entropy rates, and compression

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2006年第4期72卷 760-782页

作者： Hitchcock, John M. Vinodchandran, N. V. Univ Wyoming Dept Comp Sci Laramie WY 82071 USA Univ Nebraska Dept Comp Sci & Engn Lincoln NE 68588 USA

This paper develops new relationships between resource-bounded dimension, entropy rates, and compression. New tools for calculating dimensions are given and used to improve previous results about circuit-size complexity classes. Approximate counting of SpanP functions is used to prove that the NP-entropy rate is an upper bound for dimension in Delta(E)(3), the third level of the exponential-time hierarchy. This general result is applied to simultaneously improve the results of Mayordomo [E. Mayordomo, Contributions to the study of resource-bounded measure, PhD thesis, Universitat Politecnica de Catalunya, 1994] on the measure on P/poly in Delta(E)(3) and of Lutz [J.H. Lutz, Dimension in complexity classes, SIAM J. Comput. 32 (5) (2003) 1236-1259] on the dimension of exponential-size circuit complexity classes in ESPACE. Entropy rates of efficiently rankable sets, sets that are optimally compressible, are studied in conjunction with time-bounded dimension. It is shown that rankable entropy rates give upper bounds for time-bounded dimensions. We use this to improve results of Lutz [J.H. Lutz, Almost everywhere high nonuniform complexity, J. Comput. System Sci. 44 (2) (1992) 220-258] about polynomial-size circuit complexity classes from resource-bounded measure to dimension. Exact characterizations of the effective dimensions in terms of Kolmogorov complexity rates at the polynomial-space and higher levels have been established, but in the time-bounded setting no such equivalence is known. We introduce the concept of polynomial-time superranking as an extension of ranking. We show that superranking provides an equivalent definition of polynomial-time dimension. From this superranking characterization we show that polynomial-time Kolmogorov complexity rates give a lower bound on polynomial-time dimension. (C) 2005 Elsevier Inc. All rights reserved.

关键词： resource-bounded dimension scaled dimension Hausdorff dimension gales circuit complexity Kolmogorov complexity computational complexity

来源：评论

学校读者我要写书评

暂无评论

Numerical evaluation of methods approximating the distribution of a large quadratic form in normal variables

引用

computational STATISTICS & DATA ANALYSIS 2019年 139卷 75-81页

作者： Chen, Tong Lumley, Thomas Univ Auckland Auckland New Zealand

Quadratic forms of Gaussian variables occur in a wide range of applications in statistics. They can be expressed as a linear combination of chi-squareds. The coefficients in the linear combination are the eigenvalues lambda(1),.., lambda(n) of Sigma A, where A is the matrix representing the quadratic form and Sigma is the covariance matrix of the Gaussians. The previous literature mostly deals with approximations for small quadratic forms (n < 10) and moderate p-values (p > 10(-2)). Motivated by genetic applications, moderate to large quadratic forms (300 < n < 12, 000) and small to very small p-values (p < 10(-4)) are studied. Existing methods are compared under these settings and a leading-eigenvalue approximation, which only takes the largest k eigenvalues, is shown to have the computational advantage without any important loss in accuracy. For time complexity, a leading-eigenvalue approximation reduces the computational complexity from O(n(3)) to O(n(2)k) on extracting eigenvalues and avoids speed problems with computing the sum of n terms. For accuracy, the existing methods have some limits in calculating small p-values under large quadratic forms. Moment methods are inaccurate for very small p-values, and Farebrother's method is not usable if the minimum eigenvalue is much smaller than others. Davies's method is usable for p-values down to machine epsilon. The saddlepoint approximation is proved to have bounded relative error for any A and Sigma in the extreme right tail, so it is usable for arbitrarily small p-values. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Small p-values Leading-eigenvalue approximation Accuracy computational complexity

来源：评论

学校读者我要写书评

暂无评论

Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time

引用

FOUNDATIONS OF computational MATHEMATICS 2023年第6期23卷 1959-2047页

作者： Banks, Jess Garza-Vargas, Jorge Kulkarni, Archit Srivastava, Nikhil Univ Calif Berkeley Dept Math Berkeley CA 94720 USA

We exhibit a randomized algorithm which, given a square matrix A is an element of C-nxn with parallel to A parallel to 0, computes with high probability an invertible V and diagonal D such that parallel to A - V DV-1... 详细信息

We exhibit a randomized algorithm which, given a square matrix A is an element of C-nxn with parallel to A parallel to <= 1 and delta > 0, computes with high probability an invertible V and diagonal D such that parallel to A - V DV-1 parallel to <= delta using 0(T-MM (n) log(2) (n /delta)) arithmetic operations, in finite arithmetic with O(log(4) (n/delta) log n) bits of precision. The computed similarity V additionally satisfies parallel to V parallel to parallel to V-1 parallel to <= O(n(2.5)/delta). Here T-MM(n) is the number of arithmetic operations required to multiply two n x n complex matrices numerically stably, known to satisfy T-MM(n) = O(n(omega+eta)) for every eta > 0 where omega is the exponent of matrix multiplication (Demmel et al. in Numer Math 108(1):59-91, 2007). The algorithm is a variant of the spectral bisection algorithm in numerical linear algebra (Beavers Jr. and Denman in Numer Math 21(1-2):143-169, 1974) with a crucial Gaussian perturbation preprocessing step. Our result significantly improves the previously best-known provable running times of O(n(10)/delta(2)) arithmetic operations for diagonalization of general matrices (Armentano et al. in J Eur Math Soc 20(6):1375-1437, 2018) and (with regard to the dependence on n) O(n(3)) arithmetic operations for Hermitian matrices (Dekker and Traub in Linear Algebra Appl 4:137-154, 1971). It is the first algorithm to achieve nearly matrix multiplication time for diagonalization in any model of computation (real arithmetic, rational arithmetic, or finite arithmetic), thereby matching the complexity of other dense linear algebra operations such as inversion and QR factorization up to polylogarithmic factors. The proof rests on two new ingredients. (1) We show that adding a small complex Gaussian perturbation to any matrix splits its pseudospectrum into n small well-separated components. In particular, this implies that the eigenvalues of the perturbed matrix have a large minimum gap, a property of in

关键词： Linear algebra Random matrix theory Numerical analysis computational complexity

来源：评论

学校读者我要写书评

暂无评论

Tractability in constraint satisfaction problems: a survey

引用

CONSTRAINTS 2016年第2期21卷 115-144页

作者： Carbonnel, Clement Cooper, Martin C. CNRS LAAS 7 Ave Colonel Roche F-31400 Toulouse France Univ Toulouse INP Toulouse LAAS F-31400 Toulouse France Univ Toulouse 3 IRIT F-31062 Toulouse France

Even though the Constraint Satisfaction Problem (CSP) is NP-complete, many tractable classes of CSP instances have been identified. After discussing different forms and uses of tractability, we describe some landmark tractable classes and survey recent theoretical results. Although we concentrate on the classical CSP, we also cover its important extensions to infinite domains and optimisation, as well as #CSP and QCSP.

关键词： computational complexity Polynomial-time Dichotomy Tractable language Polymorphism Microstructure Forbidden pattern Relaxation

来源：评论

学校读者我要写书评

暂无评论

Non-symbolic algorithms for the inversion of tridiagonal matrices

引用

JOURNAL OF computational AND APPLIED MATHEMATICS 2013年 252卷 3-11页

作者： Abderraman Marrero, J. Rachidi, M. Tomeo, V. Tech Univ Madrid ETSIT UPM Telecommun Engn Sch Dept Math Appl Informat Technol Madrid 28040 Spain Univ Moulay Ismail Fac Sci Dept Math & Informat Grp DEFA Beni Mhamed Meknes Morocco Univ Complutense EUE UCM Sch Stat Dept Algebra E-28040 Madrid Spain

A representation for the entries of the inverse of general tridiagonal matrices is based on the determinants of their principal submatrices. It enables us to introduce, through the linear recurrence relations satisfied by such determinants, a simple algorithm for the entries of the inverse of any tridiagonal nonsingular matrix, reduced as well as unreduced. The numerical approach is preserved here, without invoking the symbolic computation. For tridiagonal diagonally dominant matrices, a scaling transformation on the recurrences allows us to give another algorithm to avoid overflow and underflow. (C) 2012 Elsevier B.V. All rights reserved.

关键词： computational complexity Difference equation Inverse matrix Numerical algorithm Tridiagonal matrix

来源：评论

学校读者我要写书评

暂无评论

Transmit Beamforming Optimization Design for Broadband Multigroup Multicast System

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2015年第1期2015卷 1-13页

作者： Zhang, Zilong Xu, Xiaodong Wu, Yanan Chinese Acad Sci Univ Sci & Technol China Sch Informat Sci & Technol Key Lab Wireless Opt Commun Hefei 230027 Anhui Peoples R China Nanjing Forest Police Coll Dept Detect Nanjing 210023 Jiangsu Peoples R China

Spectral efficient transmission techniques are necessary and promising for future broadband wireless communications, where the quality of service (QoS) and/or max-min fair (MMF) of intended users are often considered simultaneously. In this paper, both the QoS problem and the MMF problem are investigated together for transmit beamforming in broadband multigroup multicast channels with frequency-selective fading characters. We first present a basic algorithm by directly using the results in frequency-flat multigroup multicast systems (Karipidis et al., 2008), namely, the approximation algorithms in this paper, for both problems, respectively. Due to high computational consumption nature of the approximation algorithms, two reduced-complexity algorithms for each of the two problems are proposed separately by introducing the time-frequency correlations. In addition, parameters in the new time-frequency formulations, such as the number of optimization matrix variables and the taps of the beamformer with finite impulse response (FIR) structure, can be used to make a reasonable tradeoff between computational burden and system performance. Insights into the relationship between the two problems and some analytical results of the computational complexity of the proposed algorithms are also studied carefully. Numerical simulations indicate the efficiency of the proposed algorithms.

关键词： BEAMFORMING MULTICASTING (Computer networks) WIRELESS communication systems QUALITY of service APPROXIMATION algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

Radio Resource Management for C-V2X: From a Hybrid Centralized-Distributed Scheme to a Distributed Scheme

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2023年第4期41卷 1023-1034页

作者： Guo, Chi Wang, Cong Cui, Lin Zhou, Qiuzhan Li, Juan Jilin Univ Coll Commun Engn Changchun 130022 Peoples R China

Spectrum sharing in cellular vehicle-to-everything (C-V2X) has been conceived as a promising solution to improve spectrum efficiency. However, the co-channel interference incurred with it may cause severe performance degradation to vehicular links. Thereby, radio resource management (RRM) is motivated and designed to ensure communication reliability and increase system capacity. One challenge is that RRM involves channel allocation and power control, which are tightly coupled and hard to optimize simultaneously. Another challenge for this is the difficulty adapting centralized RRM schemes, requiring global channel state information (CSI) and causing high signaling overhead. To tackle these challenges, we propose the hybrid centralized-distributed RRM scheme and the distributed RRM scheme. Specifically, we prove a decoupling method that provides a theoretical lower bound so that channel allocation and power control can be optimized independently. Given the decoupling method, the hybrid centralized-distributed RRM scheme is based on graph matching and reinforcement learning (GMRL) to maximize system capacity and guarantee reliability requirements. Further, to decrease computation complexity and signaling overhead, the distributed RRM scheme that only requires local CSI with hybrid-framework reinforcement learning (HFRL) is exploited. Finally, both schemes are numerically evaluated through experiments and outperform other deep Q-network (DQN)-based schemes.

关键词： Reliability Channel allocation Resource management Power control Optimization Distributed algorithms computational complexity C-V2X radio resource management graph matching reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

Disjoint motif discovery in biological network using pattern join method

引用

IET SYSTEMS BIOLOGY 2019年第5期13卷 213-224页

作者： Patra, Sabyasachi Mohapatra, Anjali IIIT Bhubaneswar Dept Comp Sci Bhubaneswar Odisha India

The biological network plays a key role in protein function annotation, protein superfamily classification, disease diagnosis, etc. These networks exhibit global properties like small-world property, power-law degree distribution, hierarchical modularity, robustness, etc. Along with these, the biological network also possesses some local properties like clustering and network motif. Network motifs are recurrent and statistically over-represented subgraphs in a target network. Operation of a biological network is controlled by these motifs, and they are responsible for many biological applications. Discovery of network motifs is a computationally hard problem and involves a subgraph isomorphism check which is NP-complete. In recent years, researchers have developed various tools and algorithms to detect network motifs efficiently. However, it is still a challenging task to discover the network motif within a practical time bound for the large motif. In this study, an efficient pattern-join based algorithm is proposed to discover network motif in biological networks. The performance of the proposed algorithm is evaluated on the transcription regulatory network of Escherichia coli and the protein interaction network of Saccharomyces cerevisiae. The running time of the proposed algorithm outperforms most of the existing algorithms to discover large motifs.

关键词： graph theory bioinformatics network theory (graphs) complex networks pattern classification microorganisms proteins computational complexity diseases molecular biophysics genetics Saccharomyces cerevisiae Escherichia coli pattern join method disjoint motif discovery protein interaction network transcription regulatory network target network network motif biological network

来源：评论

学校读者我要写书评

暂无评论

Mechanism Design for Base Station Association and Resource Allocation in Downlink OFDMA Network

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2012年第11期30卷 2238-2250页

作者： Hong, Mingyi Garcia, Alfredo Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA Univ Virginia Dept Syst & Informat Engn Charlottesville VA 22903 USA Univ Minnesota Digital Technol Ctr Minneapolis MN 55455 USA

We consider a resource management problem in a multi-cell downlink OFDMA network whereby the goal is to find the optimal combination of (i) assignment of users to base stations and (ii) resource allocation strategies at each base station. Efficient resource management protocols must rely on users truthfully reporting privately held information such as downlink channel states. However, individual users can manipulate the resulting resource allocation (by misreporting their private information) if by doing so they can improve their payoff. Therefore, it is of interest to design efficient resource management protocols that are strategy-proof, i. e. it is in the users' best interests to truthfully report their private information. Unfortunately, we show that the implementation of any protocol that is efficient and strategy-proof is NP-hard. Thus, we propose a computationally tractable strategy-proof mechanism that is approximately efficient, i. e. the solution obtained yields at least 1 2 of the optimal throughput. Simulations are provided to illustrate the effectiveness of the proposed mechanism.

关键词： Heterogenous Network Mechanism Design Resource Allocation Base Station Association Approximation Bounds computational complexity Nash Equilibrium Price of Anarchy

来源：评论

学校读者我要写书评

暂无评论

Characterization of the complexity of Computing the Minimum Mean Square Error of Causal Prediction

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2024年第9期70卷 6627-6638页

作者： Boche, Holger Pohl, Volker Poor, H. Vincent Tech Univ Munich Chair Theoret Informat Technol D-80333 Munich Germany BMBF Res Hub 6G Life D-80333 Munich Germany Ctr Quantum Sci & Technol MCQST D-80799 Munich Germany Munich Quantum Valley MQV D-80807 Munich Germany Princeton Univ Dept Elect & Comp Engn Princeton NJ 08544 USA

This paper investigates the complexity of computing the minimum mean square prediction error for wide-sense stationary stochastic processes. It is shown that if the spectral density of the stationary process is a strictly positive, computable continuous function then the minimum mean square error (MMSE) is always a computable number. Nevertheless, we also show that the computation of the MMSE is a #P-1 complete problem on the set of strictly positive, polynomial-time computable, continuous spectral densities. This means that if, as widely assumed, FP1 not equal #P-1 , then there exist strictly positive, polynomial-time computable continuous spectral densities for which the computation of the MMSE is not polynomial-time computable. These results show in particular that under the widely accepted assumptions of complexity theory, the computation of the MMSE is generally much harder than an $NP_{1}$ complete problem.

关键词： Stochastic processes Finite impulse response filters computational complexity Turing machines Signal processing algorithms Filtering theory Prediction algorithms Wiener prediction filter minimum mean square error computability Turing machine complexity theory complexity blowup

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：