共查询到20条相似文献,搜索用时 62 毫秒
1.
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. 相似文献
2.
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}} 相似文献
3.
We consider a finite element approximation of a phase field model for the evolution of voids by surface diffusion in an electrically
conducting solid. The phase field equations are given by the nonlinear degenerate parabolic system
4.
Andrzej Lingas 《Algorithmica》2011,61(1):36-50
We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of
the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides
the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input
size and the number of non-zero entries of the product matrix. It runs in time [(O)\tilde](n2sw/2-1)\widetilde{O}(n^{2}s^{\omega/2-1}), where the input matrices have size n×n, the number of non-zero entries in the product matrix is at most s, ω is the exponent of the fast matrix multiplication and [(O)\tilde](f(n))\widetilde{O}(f(n)) denotes O(f(n)log
d
n) for some constant d. By the currently best bound on ω, its running time can be also expressed as [(O)\tilde](n2s0.188)\widetilde{O}(n^{2}s^{0.188}). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n
1.232 and it is never slower than the fast [(O)\tilde](nw)\widetilde{O}(n^{\omega})-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further
to the form
[(O)\tilde](nw(\frac12logns,1,1))\widetilde{O}(n^{\omega(\frac{1}{2}\log_{n}s,1,1)}), where ω(p,q,t) is the exponent of the fast multiplication of an n
p
×n
q
matrix by an n
q
×n
t
matrix. 相似文献
5.
A set A is nontrivial for the linear-exponential-time class E=DTIME(2
lin
) if for any k≥1 there is a set B
k
∈E such that B
k
is (p-m-)reducible to A and Bk ? DTIME(2k·n)B_{k} \not\in \mathrm{DTIME}(2^{k\cdot n}). I.e., intuitively, A is nontrivial for E if there are arbitrarily complex sets in E which can be reduced to A. Similarly, a set A is nontrivial for the polynomial-exponential-time class EXP=DTIME(2
poly
) if for any k≥1 there is a set [^(B)]k ? EXP\hat{B}_{k} \in \mathrm {EXP} such that [^(B)]k\hat{B}_{k} is reducible to A and [^(B)]k ? DTIME(2nk)\hat{B}_{k} \not\in \mathrm{DTIME}(2^{n^{k}}). We show that these notions are independent, namely, there are sets A
1 and A
2 in E such that A
1 is nontrivial for E but trivial for EXP and A
2 is nontrivial for EXP but trivial for E. In fact, the latter can be strengthened to show that there is a set A∈E which is weakly EXP-hard in the sense of Lutz (SIAM J. Comput. 24:1170–1189, 11) but E-trivial. 相似文献
6.
We consider the following type of online variance minimization problem: In every trial t our algorithms get a covariance matrix C
t
and try to select a parameter vector w
t−1 such that the total variance over a sequence of trials ?t=1T (wt-1)T Ctwt-1\sum_{t=1}^{T} (\boldsymbol {w}^{t-1})^{\top} \boldsymbol {C}^{t}\boldsymbol {w}^{t-1} is not much larger than the total variance of the best parameter vector u chosen in hindsight. Two parameter spaces in ℝ
n
are considered—the probability simplex and the unit sphere. The first space is associated with the problem of minimizing
risk in stock portfolios and the second space leads to an online calculation of the eigenvector with minimum eigenvalue of
the total covariance matrix ?t=1T Ct\sum_{t=1}^{T} \boldsymbol {C}^{t}. For the first parameter space we apply the Exponentiated Gradient algorithm which is motivated with a relative entropy regularization.
In the second case, the algorithm has to maintain uncertainty information over all unit directions u. For this purpose, directions are represented as dyads uu
⊤ and the uncertainty over all directions as a mixture of dyads which is a density matrix. The motivating divergence for density
matrices is the quantum version of the relative entropy and the resulting algorithm is a special case of the Matrix Exponentiated
Gradient algorithm. In each of the two cases we prove bounds on the additional total variance incurred by the online algorithm
over the best offline parameter. 相似文献
7.
We investigate the diameter
problem in the streaming and sliding-window
models. We show that, for
a stream of nn points or a sliding window of size nn, any exact
algorithm for diameter requires W(n)\Omega(n) bits of
space. We present a simple e\epsilon-approximation algorithm
for computing the diameter in the streaming model. Our main result
is an e\epsilon-approximation algorithm
that maintains the diameter in two dimensions in the sliding-window
model using O((1/e3/2) log3n(logR+loglogn + log(1/e)))O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n +
\log ({1}/{\epsilon}))) bits of space, where RR is the maximum, over all
windows, of the ratio of the diameter to the minimum non-zero distance
between any two points in the window. 相似文献
8.
Battle and Lemarie derived independently wavelets by orthonormalizing B-splines. The scaling function
m
(t) corresponding to Battle–Lemarie's wavelet
m
(t) is given by
, where B
m(t) is the mth-order central B-spline and the coefficients
m, k
satisfy
. In this paper, we propose an FFT-based algorithm for computing the expansion coefficients
m, k
and the two-scale relations of the scaling functions and wavelets. The algorithm is very simple and it can be easily implemented. Moreover, the expansion coefficients can be efficiently and accurately obtained via multiple sets of FFT computations. The computational approach presented in this paper here is noniterative and is more efficient than the matrix approach recently proposed in the literature. 相似文献
9.
Yanmin Zhao Pan Chen Weiping Bu Xiangtao Liu Yifa Tang 《Journal of scientific computing》2017,70(1):407-428
Based on spatial conforming and nonconforming mixed finite element methods combined with classical L1 time stepping method, two fully-discrete approximate schemes with unconditional stability are first established for the time-fractional diffusion equation with Caputo derivative of order \(0<\alpha <1\). As to the conforming scheme, the spatial global superconvergence and temporal convergence order of \(O(h^2+\tau ^{2-\alpha })\) for both the original variable u in \(H^1\)-norm and the flux \(\vec {p}=\nabla u\) in \(L^2\)-norm are derived by virtue of properties of bilinear element and interpolation postprocessing operator, where h and \(\tau \) are the step sizes in space and time, respectively. At the same time, the optimal convergence rates in time and space for the nonconforming scheme are also investigated by some special characters of \(\textit{EQ}_1^{\textit{rot}}\) nonconforming element, which manifests that convergence orders of \(O(h+\tau ^{2-\alpha })\) and \(O(h^2+\tau ^{2-\alpha })\) for the original variable u in broken \(H^1\)-norm and \(L^2\)-norm, respectively, and approximation for the flux \(\vec {p}\) converging with order \(O(h+\tau ^{2-\alpha })\) in \(L^2\)-norm. Numerical examples are provided to demonstrate the theoretical analysis. 相似文献
10.
This paper develops and analyzes finite element Galerkin and spectral Galerkin methods for approximating viscosity solutions
of the fully nonlinear Monge-Ampère equation det (D
2
u
0)=f (>0) based on the vanishing moment method which was developed by the authors in Feng and Neilan (J. Sci. Comput. 38:74–98,
2009) and Feng (Convergence of the vanishing moment method for the Monge-Ampère equation, submitted). In this approach, the Monge-Ampère
equation is approximated by the fourth order quasilinear equation −εΔ2
u
ε
+det D
2
u
ε
=f accompanied by appropriate boundary conditions. This new approach enables us to construct convergent Galerkin numerical methods
for the fully nonlinear Monge-Ampère equation (and other fully nonlinear second order partial differential equations), a task
which has been impracticable before. In this paper, we first develop some finite element and spectral Galerkin methods for
approximating the solution u
ε
of the regularized problem. We then derive optimal order error estimates for the proposed numerical methods. In particular,
we track explicitly the dependence of the error bounds on the parameter ε, for the error ue-uehu^{\varepsilon}-u^{\varepsilon}_{h}. Due to the strong nonlinearity of the underlying equation, the standard error estimate technique, which has been widely
used for error analysis of finite element approximations of nonlinear problems, does not work here. To overcome the difficulty,
we employ a fixed point technique which strongly makes use of the stability property of the linearized problem and its finite
element approximations. Finally, using the Argyris finite element method as an example, we present a detailed numerical study
of the rates of convergence in terms of powers of ε for the error u0-uheu^{0}-u_{h}^{\varepsilon}, and numerically examine what is the “best” mesh size h in relation to ε in order to achieve these rates. 相似文献
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.
Roel Verstappen 《Journal of scientific computing》2011,49(1):94-110
Large eddy simulation (LES) seeks to predict the dynamics of spatially filtered turbulent flows. The very essence is that
the LES-solution contains only scales of size ≥Δ, where Δ denotes some user-chosen length scale. This property enables us
to perform a LES when it is not feasible to compute the full, turbulent solution of the Navier-Stokes equations. Therefore,
in case the large eddy simulation is based on an eddy viscosity model we determine the eddy viscosity such that any scales
of size <Δ are dynamically insignificant. In this paper, we address the following two questions: how much eddy diffusion is
needed to (a) balance the production of scales of size smaller than Δ; and (b) damp any disturbances having a scale of size
smaller than Δ initially. From this we deduce that the eddy viscosity ν
e
has to depend on the invariants
q = \frac12tr(S2)q = \frac{1}{2}\mathrm{tr}(S^{2}) and
r = -\frac13tr(S3)r= -\frac{1}{3}\mathrm{tr}(S^{3}) of the (filtered) strain rate tensor S. The simplest model is then given by
ne = \frac32(D/p)2 |r|/q\nu_{e} = \frac{3}{2}(\Delta/\pi)^{2} |r|/q. This model is successfully tested for a turbulent channel flow (Re
τ
=590). 相似文献
13.
Rahul Tripathi 《Theory of Computing Systems》2010,46(2):193-221
The 1-versus-2 queries problem, which has been extensively studied in computational complexity theory, asks in its generality whether every efficient
algorithm that makes at most 2 queries to a Σ
k
p
-complete language L
k
has an efficient simulation that makes at most 1 query to L
k
. We obtain solutions to this problem for hypotheses weaker than previously considered. We prove that:
14.
15.
The transformation
16.
Antoine Chaillet Yacine Chitour Antonio Loría Mario Sigalotti 《Mathematics of Control, Signals, and Systems (MCSS)》2008,20(2):135-156
Consider the controlled system dx/dt = Ax + α(t)Bu where the pair (A, B) is stabilizable and α(t) takes values in [0, 1] and is persistently exciting, i.e., there exist two positive constants μ, T such that, for every t ≥ 0, ${\int_t^{t+T}\alpha(s){\rm d}s \geq \mu}
17.
Tahmineh? Keshavarzi Farideh?Sedaghat G.?Ali?Mansoori 《Microfluidics and nanofluidics》2010,8(1):97-104
The aim of our research is to develop a theory, which can predict the behavior of confined fluids in nanoslit pores. The nanoslit
pores studied in this work consist of two structureless and parallel walls in the xy plane located at z = 0 and z = H, in equilibrium with a bulk homogeneous fluid at the same temperature and at a given uniform bulk density. We have derived
the following general equation for prediction of the normal pressure tensor P
zz
of confined inhomogeneous fluids in nanoslit pores:
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |