Search results for "computational complexity"
showing 10 items of 249 documents
Regression Wavelet Analysis for Lossless Coding of Remote-Sensing Data
2016
A novel wavelet-based scheme to increase coefficient independence in hyperspectral images is introduced for lossless coding. The proposed regression wavelet analysis (RWA) uses multivariate regression to exploit the relationships among wavelet-transformed components. It builds on our previous nonlinear schemes that estimate each coefficient from neighbor coefficients. Specifically, RWA performs a pyramidal estimation in the wavelet domain, thus reducing the statistical relations in the residuals and the energy of the representation compared to existing wavelet-based schemes. We propose three regression models to address the issues concerning estimation accuracy, component scalability, and c…
A Mesh-free Particle Method for Transient Full-wave Simulation
2007
A mesh-free particle method is presented for electromagnetic (EM) transient simulation. The basic idea is to obtain numerical solutions for the partial differential equations describing the EM problem in time domain, by using a set of particles, considered as spatial interpolation points of the field variables, arbitrarily placed in the problem domain and by avoiding the use of a regular mesh. Irregular problems geometry with diffused non-homogeneous media can be modeled only with an initial set of arbitrarily distributed particles. The time dependence is accounted for with an explicit finite difference scheme. Moreover the particle discretization can be improved during the process time ste…
On the metric properties of dynamic time warping
1987
Recently, some new and promising methods have been proposed to reduce the number of Dynamic Time Warping (DTW) computations in Isolated Word Recognition. For these methods to be properly applicable, the verification of the Triangle Inequality (TI) by the DTW-based Dissimilarity Measure utilized seems to be an important prerequisite.
A polynomial algorithm solving a special class of hybrid optimal control problems
2006
Hybrid optimal control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions [5]. In this paper, we identify a special class of hybrid optimal control problems which are easy to solve. We do this by using a paradigm borrowed from the Operations Research field. As main result, we present a solution algorithm that converges to the exact solution in polynomial time. Our approach consists in approximating the hybrid optimal control problem via an integer-linear programming reformulation. The integer-linear programming problem is a Set-covering one with a totally unimodular constraint matrix and therefore solving the S…
A multi-agent system reinforcement learning based optimal power flow for islanded microgrids
2016
In this paper, a distributed intelligence algorithm is used to manage the optimal power flow problem in islanded microgrids. The methodology provides a suboptimal solution although the error is limited to a few percent as compared to a centralized approach. The solution algorithm is multi-agent based. According to the method, couples of agents communicate with each other only if the buses where they are located are electrically connected. The overall prizing system required for learning uses a feedback from an approximated model of the network. Based on the latter, a distributed reiforcement learning algorithm is implemented to minimize the joule losses while meeting operational constraints…
On the effectiveness of Finite Element simulation of orthogonal cutting with particular reference to temperature prediction
2007
Abstract Finite Element simulation of orthogonal cutting is nowadays assuming a large relevance; in fact a very large number of papers may be found out in technical literature on this topic. In recent years, numerical simulation was performed to investigate various phenomena such as chip segmentation, force prediction and tool wear. On the other hand, some drawbacks have to be highlighted; due to the geometrical and computational complexity of the updated-Lagrangian formulation mostly used in FE codes, a cutting time of only a few milliseconds can be effectively simulated. Therefore, steady-state thermal conditions are not reached and the simulation of the thermal phenomenon may be ineffect…
On the Inner Product Predicate and a Generalization of Matching Vector Families
2018
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function $P$ and some modulus $q$. We are interested in encoding $x$ to $\vec x$ and $y$ to $\vec y$ so that $$P(x,y) = 1 \Longleftrightarrow \langle\vec x,\vec y\rangle= 0 \bmod q,$$ where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and mor…
Combinatorial proofs of two theorems of Lutz and Stull
2021
Recently, Lutz and Stull used methods from algorithmic information theory to prove two new Marstrand-type projection theorems, concerning subsets of Euclidean space which are not assumed to be Borel, or even analytic. One of the theorems states that if $K \subset \mathbb{R}^{n}$ is any set with equal Hausdorff and packing dimensions, then $$ \dim_{\mathrm{H}} π_{e}(K) = \min\{\dim_{\mathrm{H}} K,1\} $$ for almost every $e \in S^{n - 1}$. Here $π_{e}$ stands for orthogonal projection to $\mathrm{span}(e)$. The primary purpose of this paper is to present proofs for Lutz and Stull's projection theorems which do not refer to information theoretic concepts. Instead, they will rely on combinatori…
Unit contradiction versus unit propagation
2012
Some aspects of the result of applying unit resolution on a CNF formula can be formalized as functions with domain a set of partial truth assignments. We are interested in two ways for computing such functions, depending on whether the result is the production of the empty clause or the assignment of a variable with a given truth value. We show that these two models can compute the same functions with formulae of polynomially related sizes, and we explain how this result is related to the CNF encoding of Boolean constraints.
New separation between $s(f)$ and $bs(f)$
2011
In this note we give a new separation between sensitivity and block sensitivity of Boolean functions: $bs(f)=(2/3)s(f)^2-(1/3)s(f)$.