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

A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle

THEORETICAL COMPUTER SCIENCE 2008年第3期409卷 617-622页

作者： Jansen, Maurice J. Regan, Kenneth W. SUNY Buffalo Dept CSE Buffalo NY 14260 USA Univ Aarhus Dept Comp Sci DK-8200 Aarhus N Denmark

We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho-Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM journal of Applied Mathematics 49 (1989) 906-931] given by [Tao IT. Tao, An uncertainty principle for cyclic groups of prime order, Mathematical Research Letters 12 (2005) 121-127], and a combinatorial lemma by Raz and Shpilka [R. Raz, A. Shpilka, Lower bounds for matrix product, in arbitrary circuits with bounded gates, SIAM Journal of Computing 32 (2003) 488-513]. This combination and an observation on ranks of circulant matrices, which we use to give a much shorter proof of the Donoho-Stark principle, may have other applications. (C) 2008 Elsevier B.V. All rights reserved.

关键词： computational complexity Arithmetical circuits Lower bounds Constant depth bilinear circuits

来源：评论

学校读者我要写书评

暂无评论

Variational Bayesian learning for background subtraction based on local fusion feature

引用

IET COMPUTER VISION 2016年第8期10卷 884-893页

作者： Yan, Junhua Wang, Shunfei Xie, Tianxia Yang, Yong Wang, Jiayi Nanjing Univ Aeronaut & Astronaut Coll Astronaut Nanjing Jiangsu Peoples R China

To resist the adverse effect of shadow interference, illumination changes, indigent texture and scenario jitter in object detection and improve performance, a background modelling method based on local fusion feature and variational Bayesian learning is proposed. First, U-LBSP (uniform-local binary similarity patterns) texture feature, lab colour and location feature are used to construct local fusion feature. U-LBSP is modified from local binary patterns in order to reduce computational complexity and better resist the influence of shadow and illumination changes. Joint colour and location feature are introduced to deal with the problem of indigent texture and scenario jitter. Then, LFGMM (Gaussian mixture model based on local fusion feature) is updated and learned by variational Bayes. In order to adapt to dynamic changing scenarios, the variational expectation maximisation algorithm is applied for distribution parameters optimisation. In this way, the optimal number of Gaussian components as well as their parameters can be automatically estimated with less time expended. Experimental results show that the authors' method achieves outstanding detection performance especially under conditions of shadow disturbances, illumination changes, indigent texture and scenario jitter. Strong robustness and high accuracy have been achieved.

关键词： image texture object detection learning (artificial intelligence) variational techniques Bayes methods expectation-maximisation algorithm computational complexity jitter image colour analysis image fusion optimisation variational Bayesian learning background subtraction shadow interference effect illumination changes indigent texture scenario jitter object detection background modelling method U-LBSP texture feature uniform-local binary similarity pattern texture feature lab colour location feature computational complexity LFGMM Gaussian mixture model based on local fusion feature variational expectation maximisation algorithm distribution parameter optimisation Gaussian components shadow disturbances

来源：评论

学校读者我要写书评

暂无评论

Market-clearing with stochastic security - Part II: Case studies

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2005年第4期20卷 1827-1835页

作者： Bouffard, F Galiana, FD Conejo, AJ McGill Univ Dept Elect & Comp Engn Montreal PQ H3A 2A7 Canada Univ Castilla La Mancha Dept Elect Engn E-13071 Ciudad Real Spain

This paper analyzes the market-clearing formulation with stochastic security developed in its companion paper through two case studies solved using mixed-integer linear programming techniques. The generation and reserve schedules as well as the nodal prices of energy and security are assessed under various conditions such as a) line flow limits, b) when nonspinning reserve is excluded from the formulation, c) demand-side valuation of energy not served, d) generator ramping limits, and e) the set of pre-selected contingencies.

关键词： computational complexity electricity markets expected load not served marginal pricing mixed-integer linear programming reserve security stochastic unit commitment value of lost load

来源：评论

学校读者我要写书评

暂无评论

computational power of nondeterministic ordered binary decision diagrams and their subclasses

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1997年第4期E80A卷 663-669页

作者： Takagi, K Nitta, K Bouno, H Takenaga, Y Yajima, S Graduate School of Information Schience Nara Institute of Schience and Technology Ikoma-shi 630-01 Japan

Ordered Binary Decision Diagrams (OBDDs) are graph-based representations of Boolean functions which are widely used because of their good properties. In this paper, we introduce nondeterministic OBDDs (NOBDDs) and their restricted forms, and evaluate their expressive power. In some applications of OBDDs, canonicity, which is one of the good properties of OBDDs, is not necessary. In such cases, we can reduce the required amount of storage by using OBDDs in some non-canonical form. A class of NOBDDs can be used as a non-canonical form of OBDDs. In this paper, we focus on two particular methods which can be regarded as using restricted forms of NOBDDs. Our aim is to show how the size of OBDDs can be reduced in such forms from theoretical point of view. Firstly, we consider a method to solve satisfiability problem of combinational circuits using the structure of circuits as a key to reduce the NOBDD size. We show that the NOBDD size is related to the cutwidth of circuits. Secondly, we analyze methods that use OBDDs to represent Boolean functions as sets of product terms. We show that the class of functions treated feasibly in this representation strictly contains that in OBDDs and contained by that in NOBDDs.

关键词： computational complexity boolean function ordered binary decision diagram satisfiability combinational circuit cutwidth sum-of-product form zero-suppressed BDD ternary decision diagram

来源：评论

学校读者我要写书评

暂无评论

QoS-aware cell association based on traffic prediction in heterogeneous cellular networks

引用

IET COMMUNICATIONS 2017年第18期11卷 2775-2782页

作者： Qi, Yanjia Wang, Hongyu Dalian Univ Technol Sch Informat & Commun Engn Dalian 116024 Peoples R China

The mobile communication system has become increasingly complicated with the dramatic growth of user's requirement in quality of service (QoS). The high fluctuation of traffic data makes conventional cell association schemes difficult to guarantee satisfactory service in accord with traffic demand. In this study, the authors propose a novel QoS-aware cell association scheme in a heterogeneous network. Utilising traffic prediction achieved by support vector regression, the user can decide the best cell according to the future traffic demand. The authors aim at maximising the total throughput with consideration of channel gains and blocking probability in different cells and formulate the cell association as a binary combinatorial optimisation problem. Since users are selfish for their own benefits without the global information, the authors turn this problem into a game theoretical framework. To obtain the Nash equilibrium with low computation complexity, a heuristic dynamic selection algorithm is proposed by updating selection probability which enables each user to associate with the best cell independently. Numerical simulation results show that the proposed algorithm achieves a remarkable throughput gain. The number of satisfied users increases substantially under the different density of users compared with conventional cell association schemes.

关键词： cellular radio combinatorial mathematics computational complexity game theory optimisation quality of service regression analysis support vector machines telecommunication computing

来源：评论

学校读者我要写书评

暂无评论

On the complexity of hardness amplification

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第10期54卷 4575-4586页

作者： Lu, Chi-Jen Tsai, Shi-Chun Wu, Hsin-Lung Acad Sinica Inst Informat Sci Taipei 115 Taiwan Natl Chiao Tung Univ Dept Comp Sci & Informat Engn Hsinchu 30050 Taiwan Natl Taipei Univ Dept Comp Sci & Informat Engn Taipei Taiwan

For delta is an element of (0, 1) and k, n is an element of N, we study the task of transforming a hard function f : {0, 1}(n) -> {0, 1}, with which any small circuit disagrees on (1 - delta)/2 fraction of the input, into a harder function f', with which any small circuit disagrees on (1 - delta(k))/2 fraction of the input. First, we show that such hardness amplification, when carried out in some black-box way, must require a high complexity. In particular, it cannot be realized by a circuit of depth d and size 2(o(k1/d)) or by a nondeterministic circuit of size o(k/log k) (and arbitrary depth) for any delta is an element of (0, 1). This extends the result of Viola, which only works when (1 - delta)/2 is small enough. Furthermore, we show that even without any restriction on the complexity of the amplification procedure, such a black-box hardness amplification must be inherently nonuniform in the following sense. To guarantee the hardness of the resulting function f', even against uniform machines, one has to start with a function f, which is hard against nonuniform algorithms with Omega(k log(1/delta)) bits of advice. This extends the result of Trevisan and Vadhan, which only addresses the case with (1 - delta)/2 = 2(-n). Finally, we derive similar lower bounds for any black-box construction of a pseudorandom generator (PRG) from a hard function. To prove our results, we link the task of hardness amplifications and PRG constructions, respectively, to some type of error-reduction codes, and then we establish lower bounds for such codes, which we hope could find interest in both coding theory and complexity theory.

关键词： computational complexity hardness amplification list-decodable code pseudorandom generator

来源：评论

学校读者我要写书评

暂无评论

Assigning Rated Items to Locations in Non-List Display Layouts

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2020年第2期26卷 1278-1291页

作者： Santini, Simone Univ Autonoma Madrid Escuela Politecn Super Madrid 28043 Spain

One of the most common ways in which results are displayed by an information retrieval system is in the form of a list, in which the most relevant results appear in the first positions. Todays large screens, however, allow one to create more complex displays of results, especially in cases such as image retrieval, in which each unit returned is fairly compact. For these layouts the simple list model is no longer valid, since the relations between the slots in which the results are placed do not form a sequence, that is, the relation among them is no longer that of a total order. In this paper we model these layouts as partial orders and show that a "stalwart display" property (a layout in which items' relevance is unambiguously conveyed by their display position) can be obtained only in the case of lists. For the other layouts, we define two classes of representation functions: "safe" functions (which display results without adding spurious structure) and "rich" functions (which do not drop any structure from the result set), as well as an algorithm to optimally display fully ordered result sets in arbitrary display layouts.

关键词： Layout Information retrieval Data models Standards computational modeling Image retrieval Display layout prominence determination attention fixation computational complexity display functions query results display

来源：评论

学校读者我要写书评

暂无评论

LINEAR TIME ALGORITHMS FOR 2-VARIABLE AND 3-VARIABLE LINEAR-PROGRAMS

引用

SIAM JOURNAL ON COMPUTING 1984年第1期13卷 31-45页

作者： DYER, ME Teesside Polytechnic Dep of Mathematics & Statistics Middlesbrough Engl Teesside Polytechnic Dep of Mathematics & Statistics Middlesbrough Engl

$O(n)$ time algorithms for linear programming problems with two or three variables and n constraints are described. The approach uses convexity, dominance of linear functions and linear-time median finding algorithms.... 详细信息

关键词： linear programming computational complexity geometric algorithm

来源：评论

学校读者我要写书评

暂无评论

Robust adaptive beamforming in impulsive noise environments

引用

IET RADAR SONAR AND NAVIGATION 2019年第12期13卷 2145-2150页

作者： Hajiabadi, Mojtaba Radmanesh, Hamid Samkan, Mahmood Ferdowsi Univ Mashhad Elect Engn Dept Mashhad Razavi Khorasan Iran Shahid Sattari Aeronaut Univ Sci & Technol Elect Engn Dept Tehran Iran

Adaptive beamforming is one of the most important parts of a smart antenna. The most existing adaptive algorithms are based on the second-order-moment of the error signal like least-mean-square and recursive-least-square (RLS) algorithms. Although these algorithms are popular, their performances are not robust in impulsive noise environments. A linearly constrained correntropy-based adaptive algorithm to solve the beamforming problem in impulsive noises is proposed in this study. The kernel width parameter of the proposed algorithm is considered to be time-varying to deal with non-stationary and impulsive environments. Simulation results illustrate that the proposed beamforming algorithm has a robust performance in impulsive noise. Moreover, the computational complexity of the authors' algorithm is less than the recent algorithms presented in this literature.

关键词： computational complexity array signal processing adaptive antenna arrays least squares approximations impulse noise robust performance authors robust adaptive beamforming impulsive noise environments smart antenna existing adaptive algorithms second-order-moment error signal like least-mean-square recursive-least-square adaptive algorithm beamforming problem impulsive environments beamforming algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Cauchy distribution based quantum state preparation by using the comparison algorithm

引用

AIP ADVANCES 2021年第10期11卷 1-8页

作者： Wang, Ethan Homestead High Sch 5000 W Mequon Rd Mequon WI 53092 USA

The quantum Monte Carlo algorithm can provide significant speedup compared to its classical counterpart. So far, most reported works have utilized Grover's state preparation algorithm. However, this algorithm relies on costly controlled Y rotations to apply the correct amplitudes onto the superposition states. Recently, a comparison-based state preparation method was proposed to reduce computational complexity by avoiding rotation operations. One critical aspect of this method is the generation of the comparison threshold associated with the amplitude of the quantum superposition states. The direct computation of the comparison threshold is often very costly. An alternative is to estimate the threshold with a Taylor approximation. However, Taylor approximations do not work well with heavy-tailed distribution functions such as the Cauchy distribution, which is widely used in applications such as financial modeling. Therefore, a new state preparation method needs to be developed. In this study, an efficient comparison-based state preparation method is proposed for the heavy-tailed Cauchy distribution. Instead of a single Taylor approximation for the entire function domain, this study uses quantum piecewise arithmetic to increase accuracy and reduce computational cost. The proposed piecewise function is in the simplest form to estimate the comparison threshold associated with the amplitudes. Numerical analysis shows that the number of required subdomains increases linearly as the maximum tolerated approximation error decreases exponentially. 197 subdomains are required to keep the error below 18192 of the maximum amplitude. Quantum parallelism ensures that the computational complexity of estimating the amplitudes is independent from the number of subdomains. (c) 2021 Author(s). All article content, except where otherwise noted, is licensed under a Creative Commons Attribution (CC BY) license (http://***/licenses/by/4.0/).

关键词： computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：