New Upper Matrix Bounds with Power Form for the Solution of the Continuous Coupled Algebraic Riccati Matrix Equation

In this paper, using the structure and coefficient matrix of the continuous coupled algebraic Riccati matrix equation (CCARE), we firstly construct positive definite matrices with power form. Then, applying the variant of the CCARE and inequalities of positive definite matrices, utilizing the characteristics of special matrices and eigenvalue inequalities, we propose new upper matrix bounds with power form for the solution of the CCARE, which improve and extend some of the recent results. Finally, we give corresponding numerical examples to illustrate the effectiveness of the derived results.     

New Worst-Case Upper Bounds for SAT

In 1980 Monien and Speckenmeyer proved that satisfiability of a propositional formula consisting of K clauses (of arbitrary length) can be checked in time of the order 2 ^{K / 3}. Recently Kullmann and Luckhardt proved the worst-case upper bound 2 ^{L / 9}, where L is the length of the input formula. The algorithms leading to these bounds are based on the splitting method, which goes back to the Davis–Putnam procedure. Transformation rules (pure literal elimination, unit propagation, etc.) constitute a substantial part of this method. In this paper we present a new transformation rule and two algorithms using this rule. We prove that these algorithms have the worst-case upper bounds 2^{0. 30897 K} and 2^{0. 10299 L} , respectively.     

Lower and Upper Bounds for Linkage Discovery

For a real-valued function f defined on {0,1}n , the linkage graph of f is a hypergraph that represents the interactions among the input variables with respect to f . In this paper, lower and upper bounds for the number of function evaluations required to discover the linkage graph are rigorously analyzed in the black box scenario. First, a lower bound for discovering linkage graph is presented. To the best of our knowledge, this is the first result on the lower bound for linkage discovery. The investigation on the lower bound is based on Yao's minimax principle. For the upper bounds, a simple randomized algorithm for linkage discovery is analyzed. Based on the Kruskal-Katona theorem, we present an upper bound for discovering the linkage graph. As a corollary, we rigorously prove that O(n ²logn) function evaluations are enough for bounded functions when the number of hyperedges is O(n), which was suggested but not proven in previous works. To see the typical behavior of the algorithm for linkage discovery, three random models of fitness functions are considered. Using probabilistic methods, we prove that the number of function evaluations on the random models is generally smaller than the bound for the arbitrary case. Finally, from the relation between the linkage graph and the Walsh coefficients, it is shown that, for bounded functions, the proposed bounds are eventually the bounds for finding the Walsh coefficients.     

Upper and Lower Bounds for Selection on the Mesh

A distance-optimal algorithm for selection on the mesh has proved to be elusive, although distance-optimal algorithms for the related problems of routing and sorting have recently been discovered. In this paper we explain, using the notion of adaptiveness, why techniques used in the currently best selection algorithms cannot lead to a distance-optimal algorithm. For worst-case inputs we apply new techniques to improve the previous best upper bound of 1.22n of Kaklamanis et al. [7] to 1.15n . This improvement is obtained in part by increasing the adaptiveness of previous algorithms. Received May 25, 1995; revised June 1, 1996.     

最坏情况下X2SAT问题的上界

最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的O(1.4511n)提高到O(1.4203n),其中n为X2SAT公式中变量的数目.X2SAT问题实例的大小不仅依赖于变量的数目还依赖于公式的长度,时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算法X2SAT-L,并从公式长度的角度证明了X2SAT问题在O(1.3643l)时间上界内可解.     

Upper Bounds for Monotone Planar Circuit Value and Variants

The P-complete Circuit Value Problem CVP, when restricted to monotone planar circuits MPCVP, is known to be in NC³, and for the special case of upward stratified circuits, it is known to be in LogDCFL. In this paper we re-examine the complexity of MPCVP, with special attention to circuits with cylindrical embeddings. We characterize cylindricality, which is stronger than planarity but strictly generalizes upward planarity, and make the characterization partially constructive. We use this construction, and four key reduction lemmas, to obtain several improvements. We show that stratified cylindrical monotone circuits can be evaluated in LogDCFL, and arbitrary cylindrical monotone circuits can be evaluated in AC¹(LogDCFL), while monotone circuits with one-input-face planar embeddings can be evaluated in LogCFL. For monotone circuits with focused embeddings, we show an upper bound of AC¹(LogDCFL). We re-examine the NC³ algorithm for general MPCVP, and note that it is in AC¹(LogCFL) = SAC². Finally, we consider extensions beyond MPCVP. We show that monotone circuits with toroidal embeddings can, given such an embedding, be evaluated in NC. Also, special kinds of arbitrary genus circuits can also be evaluated in NC. We also show that planar non-monotone circuits with polylogarithmic negation-height can be evaluated in NC.     

无线传感器网络通信性能确定上界研究

无线传感器网络一般具有实时性,其端到端通信性能上界研究具有重要意义.基于确定性网络演算理论,对无线传感器网络为保证实时数据优先的数据转发调度策略进行了性能分析与评价.建立了基于确定性网络演算的端到端通信性能分析模型,经过理论分析得到了无线传感器网络节点的数据队列上界、端到端数据流的延迟上界以及端到端数据流的延迟抖动上界.仿真结果表明基于网络演算理论的无线传感器网络性能上界均在理论计算的上界范围之内.本文的研究使得对无线传感器网络通信性能的研究更符合完备性的要求.     

On Upper Bounds for the Decoding Error Probability of Convolutional Codes

A new approach to upper bounding the decoding error probability of convolutional codes is proposed. Its idea is, instead of evaluating the individual contribution of each fundamental path, to compare it with contribution of another (lighter) fundamental path. This allows us to (1) take into account the dependence between different fundamental paths based on the code tree structure; (2) represent the decoding error probability through the contribution of the first fundamental paths and a correction factor; (3) get much more accurate estimates.     

Upper and Lower Bounds on the Learning Curve for Gaussian Processes

In this paper we introduce and illustrate non-trivial upper and lower bounds on the learning curves for one-dimensional Guassian Processes. The analysis is carried out emphasising the effects induced on the bounds by the smoothness of the random process described by the Modified Bessel and the Squared Exponential covariance functions. We present an explanation of the early, linearly-decreasing behavior of the learning curves and the bounds as well as a study of the asymptotic behavior of the curves. The effects of the noise level and the lengthscale on the tightness of the bounds are also discussed.     

Improved Upper Bounds for the Rate of Separating and Completely Separating Codes

Problems of Information Transmission - A binary code is said to be an $$(s,ell)$$ -separating code if for any two disjoint sets of its codewords of cardinalities at most $$s$$ and $$ell$$...     

Closed-Form Upper Bounds in Static Cost Analysis

The classical approach to automatic cost analysis consists of two phases. Given a program and some measure of cost, the analysis first produces cost relations (CRs), i.e., recursive equations which capture the cost of the program in terms of the size of its input data. Second, CRs are converted into closed-form, i.e., without recurrences. Whereas the first phase has received considerable attention, with a number of cost analyses available for a variety of programming languages, the second phase has been comparatively less studied. This article presents, to our knowledge, the first practical framework for the generation of closed-form upper bounds for CRs which (1) is fully automatic, (2) can handle the distinctive features of CRs, originating from cost analysis of realistic programming languages, (3) is not restricted to simple complexity classes, and (4) produces reasonably accurate solutions. A key idea in our approach is to view CRs as programs, which allows applying semantic-based static analyses and transformations to bound them, namely our method is based on the inference of ranking functions and loop invariants and on the use of partial evaluation.     

LTV Model Reduction With Upper Error Bounds

A new approach for computing upper error bounds for reduced-order models of linear time-varying systems is presented. It is based on a transformation technique of the Hankel singular values using positive-real, odd incremented functions. By applying such time-varying functions, the singular values to be removed can be forced to become equal and constant, so that they can be reduced. Two variations of this method are proposed: one for finite-time horizons and the other for infinite-time problems including periodic systems.      

基于联合概率矩阵分解的上下文广告推荐算法

上下文广告与用户兴趣及网页内容相匹配,可增强用户体验并提高广告点击率.而广告收益与广告点击率直接相关,准确预测广告点击率是提高上下文广告收益的关键.目前,上下文广告推荐面临如下问题:(1) 网页数量及用户数量规模很大;(2) 历史广告点击数据十分稀疏,导致点击率预测准确率低.针对上述问题,提出一种基于联合概率矩阵分解的因子模型AdRec,它结合用户、广告和网页三者信息进行广告推荐,以解决数据稀疏时点击率预测准确率低的问题.算法复杂度随着观测数据数量的增加呈线性增长,因此可应用于大规模数据.     

Upper and Lower Bounds for Randomized Search Heuristics in Black-Box Optimization

Randomized search heuristics like local search, tabu search, simulated annealing, or all kinds of evolutionary algorithms have many applications. However, for most problems the best worst-case expected run times are achieved by more problem-specific algorithms. This raises the question about the limits of general randomized search heuristics. Here a framework called black-box optimization is developed. The essential issue is that the problem but not the problem instance is knownto the algorithm which can collect information about the instance only by asking for the value of points in the search space. All known randomized search heuristics fit into this scenario. Lower bounds on the black-box complexity of problems are derived without complexity theoretical assumptions and are compared with upper bounds in this scenario.     

最简多元最小上界算法研究

求概念的近似是近似查询中的关键问题,其质3决定了近似查询的质量。现有的基于概念最小上界和最大下界的近似查询方法,只考虑了异构本体概念间一对一的蕴涵关系,是无法得到概念的最佳近似,近似的质量有时是不可接受的。先把最小上近似转化为多元界中最小上界问题,再把最小上界转化为最简多元最小上界问题来研究。这种把求概念的最小上近似间接转化为求概念的最简多元最小上界方法,可以大大提高最小上近似的质量,进而提高近似查询的查准率和查全率。     

Upper Bounds on Peaks in Discrete-Time Linear Systems

Trajectories of stable linear systems with nonzero initial conditions are known to deviate considerably from the zero equilibrium point at finite time instances. In the paper we analyze transients in discrete-time linear systems and provide upper bounds on deviations (peaks) via use of linear matrix inequalities. An approach to peak-minimizing feedback design is also proposed. An analysis of peak effects for norms of powers of Schur stable matrices is presented and a robust version of the problem is considered. The theory is illustrated by numerical examples.     

Lower Eigenvalue Bounds on Summation for the Solution of the Lyapunov Matrix Differential Equation

In this paper, we offer several lower bounds on eigenvalue summation for the solution of the Lyapunov matrix differential equation applying index matrix eigenvalue inequalities and Hölder inequality. Further, we give a numerical example to illustrate the effectiveness of the derived bounds.     

基于受约束偏置的概率矩阵分解算法

在概率矩阵分解(PMF)模型拟合之后,评分较少用户的特征趋近于先验分布的平均值,导致对其评分预测接近物品的平均评分.受约束概率矩阵分解(CPMF)未考虑到不同评分系统的整体差异以及数据集内部用户与物品存在的固有属性.针对以上问题,提出将传统矩阵分解中的用户和物品偏置项以及全局平均分结合受约束概率矩阵分解来建立新的矩阵分解算法.算法利用整体平均分衡量不同评分系统,在采用偏置来表示用户以及物品之间相互独立的属性的同时,引入约束使行为相近用户拥有相近的用户偏置,从而提高预测精度.在两个真实数据集上的实验结果表明,该算法相对于PMF和CPMF算法预测精度得到了提高.     

基于改进带偏置概率矩阵分解算法的研究

针对个性化推荐过程中高维稀疏性问题,本文提出一种将奇异值分解技术和带偏置概率矩阵分解相结合的推荐方法。 首先利用SVD算法初始化用户项目潜在因子向量,避免因随机赋值而使得函数陷入局部最优解,接着将用户项目的偏置信息融入到概率矩阵分解算法中,同时为了提升训练速度和推荐精度,通过动量加速的迷你批量梯度下降（mini Batch Gradient Descent,miniBGD）来训练,最后利用分解后的两个低维矩阵对原矩阵中的未知评分进行预测,在三个公开数据集的实验结果表明,本文提出的算法相对于传统的算法能够有效的提高推荐精度,进一步缓解由数据高维稀疏性带来的推荐质量不高的问题。