共查询到20条相似文献,搜索用时 31 毫秒
1.
Davod Khojasteh Salkuyeh 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(5):953-961
In this paper, we consider the fuzzy Sylvester matrix equation AX+XB=C,AX+XB=C, where
A ? \mathbbRn ×nA\in {\mathbb{R}}^{n \times n} and
B ? \mathbbRm ×mB\in {\mathbb{R}}^{m \times m} are crisp M-matrices, C is an n×mn\times m fuzzy matrix and X is unknown. We first transform this system to an (mn)×(mn)(mn)\times (mn) fuzzy system of linear equations. Then, we investigate the existence and uniqueness of a fuzzy solution to this system. We
use the accelerated over-relaxation method to compute an approximate solution to this system. Some numerical experiments are
given to illustrate the theoretical results. 相似文献
2.
The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms,
Algorithmica 37(4):295–326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set
\mathbbS\mathbb{S}
of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of
\mathbbS\mathbb{S}
. In the case where the jobs are all intervals, we characterize such sets
\mathbbS\mathbb{S}
and give an efficient algorithm (when
\mathbbS\mathbb{S}
is finite) for determining this. We show that in general, however, the problem is NP-hard. 相似文献
3.
Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine
the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift
a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
f(x) = c1(x-a)e1+c2(x-a)e2+ ?+ct(x-a)etf(x) = c_{1}(x-\alpha)^{e_{1}}+c_{2}(x-\alpha)^{e_{2}}+ \cdots +c_{t}(x-\alpha)^{e_{t}} 相似文献
4.
We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of
arbitrary real-valued functions. That is, suppose that there exist functions f1, ?, fr\phi_{1}, \ldots , \phi_{r} : {− 1, 1}n →
\mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3 for some reals a1, ?, ar\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq
exp \{\Omega(\sqrt{n})\}$r \geq
exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority
functions, we obtain a lower bound of W(2n/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2n for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi
(1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal. 相似文献
5.
In this paper, we derive unitary Yang-Baxter
\breveR(q, j){\breve{R}(\theta, \varphi)} matrices from the
8×8 \mathbbM{8\times8\,\mathbb{M}} matrix and the 4 × 4 M matrix by Yang-Baxteration approach, where
\mathbbM/M{\mathbb{M}/M} is the image of the braid group representation. In Yang-Baxter systems, we explore the evolution of tripartite negativity
for three qubits Greenberger-Horne-Zeilinger (GHZ)-type states and W-type states and investigate the evolution of the bipartite
concurrence for 2 qubits Bell-type states. We show that tripartite entanglement sudden death (ESD) and bipartite ESD all can
happen in Yang-Baxter systems and find that ESD all are sensitive to the initial condition. Interestingly, we find that in
the Yang-Baxter system, GHZ-type states can have bipartite entanglement and bipartite ESD, and find that in some initial conditions,
W-type states have tripartite ESD while they have no bipartite Entanglement. It is worth noting that the meaningful parameter
j{\varphi} has great influence on bipartite ESD for two qubits Bell-type states in the Yang-Baxter system. 相似文献
6.
Using ideas from automata theory, we design the first polynomial deterministic identity testing algorithm for the sparse noncommutative polynomial identity testing problem. Given a noncommuting black-box polynomial
f ? \mathbb F{x1,?,xn}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables xi are noncommuting, we give a deterministic polynomial identity test that checks if C o 0C \equiv 0 and runs in time polynomial in d, n, |C|, and t. Our algorithm evaluates the black-box polynomial for xi assigned to matrices over
\mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t. 相似文献
7.
We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph
G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with
each cycle and the vector space over
\mathbbF2\mathbb{F}_{2}
generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a
minimum cycle basis of G. 相似文献
8.
For the multivariate continuous function, using constructive feedforward
L2 (\mathbbR) L^{2} (\mathbb{R}) radial basis function (RBF) neural network, we prove that a
L2 (\mathbbR) L^{2} (\mathbb{R}) RBF neural network with n + 1 hidden neurons can interpolate n + 1 multivariate samples with zero error. Then, we prove that the
L2 (\mathbbR) L^{2} (\mathbb{R}) RBF neural network can uniformly approximate any continuous multivariate function with arbitrary precision. The correctness
and effectiveness are verified through eight numeric experiments. 相似文献
9.
We study algorithms simulating a system evolving with Hamiltonian H = ?j=1m Hj{H = \sum_{j=1}^m H_j} , where each of the H
j
, j = 1, . . . ,m, can be simulated efficiently. We are interested in the cost for approximating
e-iHt, t ? \mathbbR{e^{-iHt}, t \in \mathbb{R}} , with error e{\varepsilon} . We consider algorithms based on high order splitting formulas that play an important role in quantum Hamiltonian simulation.
These formulas approximate e
−iHt
by a product of exponentials involving the H
j
, j = 1, . . . ,m. We obtain an upper bound for the number of required exponentials. Moreover, we derive the order of the optimal splitting method that minimizes our upper bound. We show significant speedups relative to previously known results. 相似文献
10.
11.
Joel Ratsaby 《Annals of Mathematics and Artificial Intelligence》2008,52(1):55-65
Consider a class of binary functions h: X→{ − 1, + 1} on an interval . Define the sample width of h on a finite subset (a sample) S ⊂ X as ω
S
(h) = min
x ∈ S
|ω
h
(x)| where ω
h
(x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function
(or trace) of the class , β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples
of cardinality m. The estimate is .
相似文献
12.
Quantitative Separation Logic and Programs with Lists 总被引:1,自引:0,他引:1
This paper presents an extension of a decidable fragment of Separation Logic for singly-linked lists, defined by Berdine et
al. (2004). Our main extension consists in introducing atomic formulae of the form ls
k
(x, y) describing a list segment of length k, stretching from x to y, where k is a logical variable interpreted over positive natural numbers, that may occur further inside Presburger constraints. We
study the decidability of the full first-order logic combining unrestricted quantification of arithmetic and location variables.
Although the full logic is found to be undecidable, validity of entailments between formulae with the quantifier prefix in
the language
$* {$\mathbbN, "\mathbbN}*\exists^* \{\exists_{\bf \mathbb{N}}, \forall_{\bf \mathbb{N}}\}^* is decidable. We provide here a model theoretic method, based on a parametric notion of shape graphs. We have implemented
our decision technique, providing a fully automated framework for the verification of quantitative properties expressed as
pre- and post-conditions on programs working on lists and integer counters. 相似文献
13.
CAO FeiLong ZHANG YongQuan & XU ZongBen College of Science China Jiliang University Hangzhou China Institute of Information System Sciences Xi’an Jiaotong University Xi’an 《中国科学F辑(英文版)》2009,52(8):1321-1327
Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T... 相似文献
14.
Lubomir V. Kolev 《Reliable Computing》2006,12(2):121-140
The paper addresses the problem of determining an outer interval solution of the parametric eigenvalue problem A(p)x = λx, A(p) ∈ ℝn×n for the general case where the matrix elements aij(p) are continuous nonlinear functions of the parameter vector p, p belonging to the interval vector p. A method for computing an interval enclosure of each eigenpair (λμ, x(μ)), μ = 1, ..., n, is suggested for the case where λμ is a simple eigenvalue. It is based on the use of an affine interval approximation of aij(p) in p and reduces, essentially, to setting up and solving a real system of n or 2n incomplete quadratic equations for each real
or complex eigenvalue, respectively. 相似文献
15.
Abstract We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we
prove the existence of a unique function in
, polyharmonic of order p on each strip
,
, and periodic in its last n variables, whose restriction to the parallel hyperplanes
,
, coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in
. The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal
-splines.
Keywords: cardinal
-splines, polyharmonic functions, multivariable interpolation
Mathematics Subject Classification (2000): 41A05, 41A15, 41A63 相似文献
16.
Vyacheslav Zavadsky 《Journal of Mathematical Imaging and Vision》2007,27(2):129-138
We study image approximation by a separable wavelet basis
and ϕ,ψ are elements of a standard biorthogonal wavelet basis in L2(ℝ). Because k1≠ k2, the supports of the basis elements are rectangles, and the corresponding transform is known as the rectangular wavelet transform. We provide a self-contained proof that if one-dimensional wavelet basis has M dual vanishing moments then the rate of approximation by N coefficients of rectangular wavelet transform is
for functions with mixed derivative of order M in each direction. These results are consistent with optimal approximation rates for such functions. The square wavelet transform
yields the approximation rate is
for functions with all derivatives of the total order M. Thus, the rectangular wavelet transform can outperform the square one if an image has a mixed derivative. We provide experimental
comparison of image approximation which shows that rectangular wavelet transform outperform the square one.
Vyacheslav Zavadsky got his M.Sc. (with distinction) in computer science and applied mathematics from Belarusian State University in 1994 and
his Ph.D. in mathematics and statistics in 1998 from Belarusian Academy of Sciences and Belarusian State University. He worked
at Institute of Mathematics of Belarusian Academy of sciences, and Belarusian center for medical technologies. He also held
progressively responsible technical and research positions in the industry: at MZOR, eBusiness technologies, and Webmotion.
At present, he is the principal software architect with Semiconductor insights. His research interests include mathematical
and statistical methods in vision; machine learning, and structural data mining. Vyacheslav is author of more then ten peer
reviewed papers and conference presentation, and 7 pending inventions. 相似文献
17.
Alexander A. Sherstov 《Computational Complexity》2010,19(1):135-150
We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R∈(f) and $D^\mu_\in
(f)$D^\mu_\in
(f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu
\{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu
\{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions
only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence
of a function f : {0, 1}n ×{0, 1}n ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which maxμ product {Dm ? (f)} = Q(1) but R ? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously
posed by the author (2007). 相似文献
18.
F. Franchini A. R. Its V. E. Korepin L. A. Takhtajan 《Quantum Information Processing》2011,10(3):325-341
We consider reduced density matrix of a large block of consecutive spins in the ground states of the XY spin chain on an infinite lattice. We derive the spectrum of the density matrix using expression of Rényi entropy in terms
of modular functions. The eigenvalues λ
n
form exact geometric sequence. For example, for strong magnetic field λ
n
= C exp(−π
τ
0
n), here τ
0 > 0 and C > 0 depend on anisotropy and magnetic field. Different eigenvalues are degenerated differently. The largest eigenvalue is
unique, but degeneracy g
n
increases sub-exponentially as eigenvalues diminish: gn ~ exp(p?{n/3}){g_{n}\sim \exp{(\pi \sqrt{n/3})}}. For weak magnetic field expressions are similar. 相似文献
19.
20.
Mirrorsymmetric matrices, which are the iteraction matrices of mirrorsymmetric structures, have important application in studying odd/even-mode decomposition of symmetric multiconductor transmission lines (MTL). In this paper we present an efficient algorithm for minimizing ${\|AXB-C\|}$ where ${\|\cdot\|}$ is the Frobenius norm, ${A\in \mathbb{R}^{m\times n}}$ , ${B\in \mathbb{R}^{n\times s}}$ , ${C\in \mathbb{R}^{m\times s}}$ and ${X\in \mathbb{R}^{n\times n}}$ is mirrorsymmetric with a specified central submatrix [x ij ] r≤i, j≤n-r . Our algorithm produces a suitable X such that AXB = C in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim. 相似文献
|