Search results for "nonlinear"
showing 10 items of 3684 documents
Quantum lower bound for inverting a permutation with advice
2014
Given a random permutation $f: [N] \to [N]$ as a black box and $y \in [N]$, we want to output $x = f^{-1}(y)$. Supplementary to our input, we are given classical advice in the form of a pre-computed data structure; this advice can depend on the permutation but \emph{not} on the input $y$. Classically, there is a data structure of size $\tilde{O}(S)$ and an algorithm that with the help of the data structure, given $f(x)$, can invert $f$ in time $\tilde{O}(T)$, for every choice of parameters $S$, $T$, such that $S\cdot T \ge N$. We prove a quantum lower bound of $T^2\cdot S \ge \tilde{\Omega}(\epsilon N)$ for quantum algorithms that invert a random permutation $f$ on an $\epsilon$ fraction of…
PageRank model of opinion formation on Ulam networks
2013
We consider a PageRank model of opinion formation on Ulam networks, generated by the intermittency map and the typical Chirikov map. The Ulam networks generated by these maps have certain similarities with such scale-free networks as the World Wide Web (WWW), showing an algebraic decay of the PageRank probability. We find that the opinion formation process on Ulam networks have certain similarities but also distinct features comparing to the WWW. We attribute these distinctions to internal differences in network structure of the Ulam and WWW networks. We also analyze the process of opinion formation in the frame of generalized Sznajd model which protects opinion of small communities.
A comparative analysis of the statistical properties of large mobile phone calling networks.
2014
Mobile phone calling is one of the most widely used communication methods in modern society. The records of calls among mobile phone users provide us a valuable proxy for the understanding of human communication patterns embedded in social networks. Mobile phone users call each other forming a directed calling network. If only reciprocal calls are considered, we obtain an undirected mutual calling network. The preferential communication behavior between two connected users can be statistically tested and it results in two Bonferroni networks with statistically validated edges. We perform a comparative analysis of the statistical properties of these four networks, which are constructed from …
PRINCIPAL POLYNOMIAL ANALYSIS
2014
© 2014 World Scientific Publishing Company. This paper presents a new framework for manifold learning based on a sequence of principal polynomials that capture the possibly nonlinear nature of the data. The proposed Principal Polynomial Analysis (PPA) generalizes PCA by modeling the directions of maximal variance by means of curves instead of straight lines. Contrarily to previous approaches PPA reduces to performing simple univariate regressions which makes it computationally feasible and robust. Moreover PPA shows a number of interesting analytical properties. First PPA is a volume preserving map which in turn guarantees the existence of the inverse. Second such an inverse can be obtained…
Probabilistic Memristive Networks: Application of a Master Equation to Networks of Binary ReRAM cells
2020
Abstract The possibility of using non-deterministic circuit components has been gaining significant attention in recent years. The modeling and simulation of their circuits require novel approaches, as now the state of a circuit at an arbitrary moment in time cannot be predicted deterministically. Generally, these circuits should be described in terms of probabilities, the circuit variables should be calculated on average, and correlation functions should be used to explore interrelations among the variables. In this paper, we use, for the first time, a master equation to analyze the networks composed of probabilistic binary memristors. Analytical solutions of the master equation for the ca…
Quantum finite multitape automata
1999
Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. Moreover, it was proved that not all regular languages can be recognized by quantum finite automata. A.Ambainis and R.Freivalds proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by a deterministic or probabilistic finite automata. This is the first result on …
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
2019
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Automata, Logic and Semantics ; 1365-8050
A quantum vocal theory of sound
2020
Concepts and formalism from acoustics are often used to exemplify quantum mechanics. Conversely, quantum mechanics could be used to achieve a new perspective on acoustics, as shown by Gabor studies. Here, we focus in particular on the study of human voice, considered as a probe to investigate the world of sounds. We present a theoretical framework that is based on observables of vocal production, and on some measurement apparati that can be used both for analysis and synthesis. In analogy to the description of spin states of a particle, the quantum-mechanical formalism is used to describe the relations between the fundamental states associated with phonetic labels such as phonation, turbule…
A novel exact representation of stationary colored Gaussian processes (fractional differential approach)
2010
A novel representation of functions, called generalized Taylor form, is applied to the filtering of white noise processes. It is shown that every Gaussian colored noise can be expressed as the output of a set of linear fractional stochastic differential equations whose solution is a weighted sum of fractional Brownian motions. The exact form of the weighting coefficients is given and it is shown that it is related to the fractional moments of the target spectral density of the colored noise.
Panel Data Analysis via Mechanistic Models
2018
Panel data, also known as longitudinal data, consist of a collection of time series. Each time series, which could itself be multivariate, comprises a sequence of measurements taken on a distinct unit. Mechanistic modeling involves writing down scientifically motivated equations describing the collection of dynamic systems giving rise to the observations on each unit. A defining characteristic of panel systems is that the dynamic interaction between units should be negligible. Panel models therefore consist of a collection of independent stochastic processes, generally linked through shared parameters while also having unit-specific parameters. To give the scientist flexibility in model spe…