Search results for "Complexity"
showing 10 items of 1094 documents
Irrelevant Features, Class Separability, and Complexity of Classification Problems
2011
In this paper, analysis of class separability measures is performed in attempt to relate their descriptive abilities to geometrical properties of classification problems in presence of irrelevant features. The study is performed on synthetic and benchmark data with known irrelevant features and other characteristics of interest, such as class boundaries, shapes, margins between classes, and density. The results have shown that some measures are individually informative, while others are less reliable and only can provide complimentary information. Classification problem complexity measurements on selected data sets are made to gain additional insights on the obtained results.
Efficient boundary integral-resonant mode expansion method implementation for full-wave analysis of passive devices based on circular waveguides with…
2013
In this study, the efficient full-wave analysis of passive devices composed of circular and arbitrarily-shaped waveguides is considered. For this purpose, the well-known boundary integral-resonant mode expansion (BI RME) method has been properly extended. Circular waveguides are used for resonant mode expansion, whereas the arbitrary contour is defined by any combination of straight, circular and elliptical segments, thus allowing the exact representation of the most widely used geometries. The proposed algorithm extends previous implementations of the BI RME method based on circular waveguides by considering circular and elliptical arcs for defining arbitrary geometries. Similarly, it allo…
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.
An Improved Detection Technique for Cyclic-Prefixed OFDM
2010
A novel Orthogonal Frequency Division Multiplexing detection technique compatible to standard (e.g. Wireless LAN) transmitters is proposed. It features enhanced error-rate performance with flexible computational complexity and robustness to imperfect channel estimation. It is based on exploitation of the redundancy available in the cyclic prefix after cancellation of interference from the preceding block. In order to show the effectiveness of our proposal, an analysis of computational complexity and a number of comparisons to the standard per-subcarrier receiver and a previously existing method in terms of error rates are reported.
Equivalence closure in the two-variable guarded fragment
2015
We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.
Population Monte Carlo Schemes with Reduced Path Degeneracy
2017
Population Monte Carlo (PMC) algorithms are versatile adaptive tools for approximating moments of complicated distributions. A common problem of PMC algorithms is the so-called path degeneracy; the diversity in the adaptation is endangered due to the resampling step. In this paper we focus on novel population Monte Carlo schemes that present enhanced diversity, compared to the standard approach, while keeping the same implementation structure (sample generation, weighting and resampling). The new schemes combine different weighting and resampling strategies to reduce the path degeneracy and achieve a higher performance at the cost of additional low computational complexity cost. Computer si…
RNN- and LSTM-Based Soft Sensors Transferability for an Industrial Process
2021
The design and application of Soft Sensors (SSs) in the process industry is a growing research field, which needs to mediate problems of model accuracy with data availability and computational complexity. Black-box machine learning (ML) methods are often used as an efficient tool to implement SSs. Many efforts are, however, required to properly select input variables, model class, model order and the needed hyperparameters. The aim of this work was to investigate the possibility to transfer the knowledge acquired in the design of a SS for a given process to a similar one. This has been approached as a transfer learning problem from a source to a target domain. The implementation of a transf…
Fermion sign problem in imaginary-time projection continuum quantum Monte Carlo with local interaction
2016
We use the Shadow Wave Function formalism as a convenient model to study the fermion sign problem affecting all projector Quantum Monte Carlo methods in continuum space. We demonstrate that the efficiency of imaginary time projection algorithms decays exponentially with increasing number of particles and/or imaginary-time propagation. Moreover, we derive an analytical expression that connects the localization of the system with the magnitude of the sign problem, illustrating this prediction through some numerical results. Finally, we discuss the fermion sign problem computational complexity and methods for alleviating its severity.
An advanced variant of an interpolatory graphical display algorithm
2004
In this paper an advanced interpolatory graphical display algorithm based on cardinal B-spline functions is provided. It is well-known that B-spline functions are a flexible tool to design various scale rapresentations of a signal. The proposed method allows to display without recursion a function at any desiderable resolution so that only initial data and opportune vectors weight are involved. In this way the structure of the algorithm is independent across the scale and a computational efficiency is reached. In this paper mono and bi-dimensional vectors weight generated by means of centered cubic cardinal B-spline functions have been supplied. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Wei…
Attentional vs computational complexity measures in observing paintings
2009
Because of the great heterogeneity of subjects and styles, esthetic perception delineates a special and elusive field of research in vision, which represents an interesting challenge for cognitive science tools. With specific regard to the role of visual complexity, in this paper we present an experiment aimed to measure this dimension in a heterogeneous set of paintings. We compared perceived time complexity measures - based on a temporal estimation paradigm - with physical and statistical properties of the paintings, obtaining a strong correlation between psychological and computational results.