Search

Many modern algorithms for inverse problems and data assimilation rely on ensemble Kalman updates to blend prior predictions with observed data. Ensemble Kalman methods often perform well with a small ensemble size, which is essential in applications where generating each particle is costly. This paper develops a non-asymptotic analysis of ensemble Kalman updates, which rigorously explains why a small ensemble size suffices if the prior covariance has moderate effective dimension due to fast spectrum decay or approximate sparsity. We present our theory in a unified framework, comparing several implementations of ensemble Kalman updates that use perturbed observations, square root filtering and localization. As part of our analysis, we develop new dimension-free covariance estimation bounds for approximately sparse matrices that may be of independent interest. [ABSTRACT FROM AUTHOR]

Training of Quantum Neural Networks can be affected by barren plateaus—flat areas in the landscape of the cost function, which impede the model optimisation. While there exist methods of dealing with barren plateaus, they could reduce the model's effective dimension—the measure of its capacity to learn. This paper therefore reports an investigation of four barren plateaus countermeasures, i.e. restricting the model's circuit depth and relying on the local cost function; layer-by-layer circuit pre-training; relying on the circuit block structure to support its initialisation; as well as, model creation without any constraints. Several experiments were conducted to analyse the impact of each countermeasure on the model training, its subsequent ability to generalise and its effective dimension. The results reveal which of the approaches enhances or impedes the quantum model's capacity to learn, which gives more predictable learning outcomes, and which is more sensitive to training data. Finally, the paper provides some recommendations on how to utilise the effective dimension measurements to assist quantum model development. [ABSTRACT FROM AUTHOR]

This paper investigates the algorithmic dimension spectra of lines in the Euclidean plane. Given any line L with slope a and vertical intercept b, the dimension spectrum sp (L) is the set of all effective Hausdorff dimensions of individual points on L. We draw on Kolmogorov complexity and geometrical arguments to show that if the effective Hausdorff dimension dim (a , b) is equal to the effective packing dimension Dim (a , b) , then sp (L) contains a unit interval. We also show that, if the dimension dim (a , b) is at least one, then sp (L) is infinite. Together with previous work, this implies that the dimension spectrum of any line is infinite. [ABSTRACT FROM AUTHOR]

In this paper we use the theory of computing to study fractal dimensions of projections in Euclidean spaces. A fundamental result in fractal geometry is Marstrand's projection theorem, which states that for every analytic set E , for almost every line L , the Hausdorff dimension of the orthogonal projection of E onto L is maximal. We use Kolmogorov complexity to give two new results on the Hausdorff and packing dimensions of orthogonal projections onto lines. The first shows that the conclusion of Marstrand's theorem holds whenever the Hausdorff and packing dimensions agree on the set E , even if E is not analytic. Our second result gives a lower bound on the packing dimension of projections of arbitrary sets. Finally, we give a new proof of Marstrand's theorem using the theory of computing. [ABSTRACT FROM AUTHOR]

Many pricing problems boil down to the computation of a high-dimensional integral, which is usually estimated using Monte Carlo. In fact, the accuracy of a Monte Carlo estimator with M simulations is given by σ M {\frac{\sigma}{\sqrt{M}}}. Meaning that its convergence is immune to the dimension of the problem. However, this convergence can be relatively slow depending on the variance σ of the function to be integrated. To resolve such a problem, one would perform some variance reduction techniques such as importance sampling, stratification, or control variates. In this paper, we will study two approaches for improving the convergence of Monte Carlo using Neural Networks. The first approach relies on the fact that many high-dimensional financial problems are of low effective dimensions. We expose a method to reduce the dimension of such problems in order to keep only the necessary variables. The integration can then be done using fast numerical integration techniques such as Gaussian quadrature. The second approach consists in building an automatic control variate using neural networks. We learn the function to be integrated (which incorporates the diffusion model plus the payoff function) in order to build a network that is highly correlated to it. As the network that we use can be integrated exactly, we can use it as a control variate. [ABSTRACT FROM AUTHOR]

We investigate the construction of early stopping rules in the nonparametric regression problem where iterative learning algorithms are used and the optimal iteration number is unknown. More precisely, we study the discrepancy principle, as well as modications based on smoothed residuals, for kernelized spectral lter learning algorithms including Tikhonov regularization and gradient descent. Our main theoretical bounds are oracle inequalities established for the empirical estimation error (xed design), and for the prediction error (random design). From these nite-sample bounds it follows that the classical discrepancy principle is statistically adaptive for slow rates occurring in the hard learning scenario, while the smoothed discrepancy principles are adaptive over ranges of faster rates (resp. higher smoothness parameters). Our approach relies on deviation inequalities for the stopping rules in the xed design setting, combined with change-of-norm arguments to deal with the random design setting. [ABSTRACT FROM AUTHOR]

Effective dimension, an indicator for the difficulty of high-dimensional integration, describes whether a function can be well approximated by low-dimensional terms or sums of low-order terms. Some problems in option pricing are believed to have low effective dimensions, which help explain the success of quasi-Monte Carlo (QMC) methods recently observed in financial engineering. This paper provides a way of studying the structure of effective dimensions by finding a proper space the function of interest belongs to and then determining the effective dimension of that space. To this end, we extend the definitions of effective dimensions to weighted function spaces with product-order-dependent weights and give bounds on norms and variances. Furthermore, we show that the proposed method is applicable to functions arising in option pricing and consequently offers some hints on the performance of QMC methods. [ABSTRACT FROM AUTHOR]

We introduce the concept of effective dimension for a wide class of metric spaces whose metric is not necessarily based on a measure. Effective dimension was defined by Lutz (Inf. Comput., 187(1), 49-79, 2003) for Cantor space and has also been extended to Euclidean space. Lutz effectivization uses gambling, in particular the concept of gale and supergale, our extension of Hausdorff dimension to other metric spaces is also based on a supergale characterization of dimension, which in practice avoids an extra quantifier present in the classical definition of dimension that is based on Hausdorff measure and therefore allows effectivization for small time-bounds. We present here the concept of constructive dimension and its characterization in terms of Kolmogorov complexity, for which we extend the concept of Kolmogorov complexity to any metric space defining the Kolmogorov complexity of a point at a certain precision. Further research directions are indicated. [ABSTRACT FROM AUTHOR]

A data processing inequality states that the quantity of shared information between two entities (e.g. signals, strings) cannot be significantly increased when one of the entities is processed by certain kinds of transformations. In this paper, we prove several data processing inequalities for sequences, where the transformations are bounded Turing functionals and the shared information is measured by the lower and upper mutual dimensions between sequences. We show that, for all sequences X, Y, and Z, if Z is computable Lipschitz reducible to X, then mdim(Z:Y)≤mdim(X:Y)andMdim(Z:Y)≤Mdim(X:Y). We also show how to derive different data processing inequalities by making adjustments to the computable bounds of the use of a Turing functional. The yield of a Turing functional ΦS with access to at most n bits of the oracle S is the smallest input m∈ℕ such that ΦS↾n(m)↑. We show how to derive reverse data processing inequalities (i.e., data processing inequalities where the transformation may significantly increase the shared information between two entities) for sequences by applying computable bounds to the yield of a Turing functional. [ABSTRACT FROM AUTHOR]

We present a dataset of close range hyperspectral images of materials that span the visible and near infrared spectrums: HyTexiLa (Hyperspectral Texture images acquired in Laboratory). The data is intended to provide high spectral and spatial resolution reflectance images of 112 materials to study spatial and spectral textures. In this paper we discuss the calibration of the data and the method for addressing the distortions during image acquisition. We provide a spectral analysis based on non-negative matrix factorization to quantify the spectral complexity of the samples and extend local binary pattern operators to the hyperspectral texture analysis. The results demonstrate that although the spectral complexity of each of the textures is generally low, increasing the number of bands permits better texture classification, with the opponent band local binary pattern feature giving the best performance. [ABSTRACT FROM AUTHOR]

We show that a sequence has effective Hausdorff dimension 1 if and only if it is coarsely similar to a Martin-Löf random sequence. More generally, a sequence has effective dimension s if and only if it is coarsely similar to a weakly s -random sequence. Further, for any s < t , every sequence of effective dimension s can be changed on density at most H − 1 ( t ) − H − 1 ( s ) of its bits to produce a sequence of effective dimension t , and this bound is optimal. [ABSTRACT FROM AUTHOR]

We give formulas which determine the effective dimensions of path semigroups over an uncountable field and of truncated path semigroups over a field which is uncountable or of characteristic zero. [ABSTRACT FROM AUTHOR]

This article presents a systematic treatment of quadrature problems for self-similar probability distributions. We introduce explicit deterministic and randomized algorithms and study their errors for integrands of fractional smoothness of Hölder-Lipschitz type. Conversely, we derive lower bounds for worst-case errors of arbitrary integration schemes that prove optimality of our algorithms in many cases. In particular, we see that the effective dimension of the quadrature problem for functions of smoothness $$q>0$$ is given by the quantization dimension of order $$q$$ of the fractal measure. [ABSTRACT FROM AUTHOR]

Consider a randomness notion $${\mathcal{C}}$$ . A uniform test in the sense of $${\mathcal{C}}$$ is a total computable procedure that each oracle X produces a test relative to X in the sense of $${\mathcal{C}}$$ . We say that a binary sequence Y is $${\mathcal{C}}$$ -random uniformly relative to X if Y passes all uniform $${\mathcal{C}}$$ tests relative to X. Suppose now we have a pair of randomness notions $${\mathcal{C}}$$ and $${\mathcal{D}}$$ where $${\mathcal{C} \subseteq \mathcal{D}}$$ , for instance Martin-Löf randomness and Schnorr randomness. Several authors have characterized classes of the form Low( $${\mathcal{C}, \mathcal{D}}$$ ) which consist of the oracles X that are so feeble that $${\mathcal{C} \subseteq \mathcal{D}^X}$$ . Our goal is to do the same when the randomness notion $${\mathcal{D}}$$ is relativized uniformly: denote by Low $${\star(\mathcal{C},\mathcal{D})}$$ the class of oracles X such that every $${\mathcal{C}}$$ -random is uniformly $${\mathcal{D}}$$ -random relative to X. (1) We show that $${X\in Low ^\star}$$ (MLR, SR) if and only if X is c.e. tt-traceable if and only if X is anticomplex if and only if X is Martin-Löf packing measure zero with respect to all computable dimension functions. (2) We also show that $${X\in Low^\star}$$ (SR, WR) if and only if X is computably i.o. tt-traceable if and only if X is not totally complex if and only if X is Schnorr Hausdorff measure zero with respect to all computable dimension functions. [ABSTRACT FROM AUTHOR]

It has been found empirically that quasi-Monte Carlo methods are often efficient for very high-dimensional problems, that is, with dimension in the hundreds or even thousands. The common explanation for this surprising fact is that those functions for which this holds true behave rather like low-dimensional functions in that only few of the coordinates have a sizeable influence on its value. However, this statement may be true only after applying a suitable orthogonal transform to the input data, like utilizing the Brownian bridge construction or principal component analysis construction. We study the effect of general orthogonal transforms on functions on R d which are elements of certain weighted reproducing kernel Hilbert spaces. The notion of Hermite spaces is defined and it is shown that there are examples which admit tractability of integration. We translate the action of the orthogonal transform of R d into an action on the Hermite coefficients and we give examples where orthogonal transforms have a dramatic effect on the weighted norm, thus providing an explanation for the efficiency of using suitable orthogonal transforms. [ABSTRACT FROM AUTHOR]

In Lemieux and Faure (2009), a construction closely related to generalized Faure sequences was introduced. Unlike generalized Faure sequences, this construction is extensible in the dimension and lends itself well to high-dimensional problems. In this paper, we consider a weighted space of functions for which this construction is particularly well suited and we use it to prove tractability in that space. This space of functions is a special case of one in which we have "finite-order weights", which were studied recently by several authors. We compare our findings with these previously obtained results and provide numerical results to illustrate the practical potential of our approach. [ABSTRACT FROM AUTHOR]

The dimension of a point x in Euclidean space (meaning the constructive Hausdorff dimension of the singleton set { x } ) is the algorithmic information density of x . Roughly speaking, this is the least real number dim ( x ) such that r × dim ( x ) bits suffice to specify x on a general-purpose computer with arbitrarily high precision 2 − r . The dimension spectrum of a set X in Euclidean space is the subset of [ 0 , n ] consisting of the dimensions of all points in X . The dimensions of points have been shown to be geometrically meaningful (Lutz 2003 [16] , Hitchcock 2005 [12] ), and the dimensions of points in self-similar fractals have been completely analyzed (Lutz and Mayordomo 2008 [18] ). Here we begin the more challenging task of analyzing the dimensions of points in random fractals. We focus on fractals that are randomly selected subfractals of a given self-similar fractal. We formulate the specification of a point in such a subfractal as the outcome of an infinite two-player game between a selector that selects the subfractal and a coder that selects a point within the subfractal. Our selectors are algorithmically random with respect to various probability measures, so our selector–coder games are, from the coder's point of view, games against nature . We determine the dimension spectra of a wide class of such randomly selected subfractals. We show that each such fractal has a dimension spectrum that is a closed interval whose endpoints can be computed or approximated from the parameters of the fractal. In general, the maximum of the spectrum is determined by the degree to which the coder can reinforce the randomness in the selector, while the minimum is determined by the degree to which the coder can cancel randomness in the selector. This constructive and destructive interference between the players' randomnesses is somewhat subtle, even in the simplest cases. Our proof techniques include van Lambalgen's theorem on independent random sequences, measure preserving transformations, an application of network flow theory, a Kolmogorov complexity lower bound argument, and a nonconstructive proof that this bound is tight. [ABSTRACT FROM AUTHOR]

Dealing with uncertainty in applications of machine learning to real-life data critically depends on the knowledge of intrinsic dimensionality (ID). A number of methods have been suggested for the purpose of estimating ID, but no standard package to easily apply them one by one or all at once has been implemented in Python. This technical note introduces scikit-dimension, an open-source Python package for intrinsic dimension estimation. The scikit-dimension package provides a uniform implementation of most of the known ID estimators based on the scikit-learn application programming interface to evaluate the global and local intrinsic dimension, as well as generators of synthetic toy and benchmark datasets widespread in the literature. The package is developed with tools assessing the code quality, coverage, unit testing and continuous integration. We briefly describe the package and demonstrate its use in a large-scale (more than 500 datasets) benchmarking of methods for ID estimation for real-life and synthetic data. [ABSTRACT FROM AUTHOR]

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes. Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous results for polynomial-time dimension haven't been found. In this paper we remedy the situation by using the natural concept of reversible time-bounded compression for finite strings. We completely characterize polynomial-time dimension in terms of polynomial-time compressors. [ABSTRACT FROM AUTHOR]

Abstract: Quasi-Monte Carlo (QMC) methods are important numerical tools in computational finance. Path generation methods (PGMs), such as Brownian bridge and principal component analysis, play a crucial role in QMC methods. Their effectiveness, however, is problem-dependent. This paper attempts to understand how a PGM interacts with the underlying function and affects the accuracy of QMC methods. To achieve this objective, we develop efficient methods to assess the impact of PGMs. The first method is to exploit a quadratic approximation of the underlying function and to analyze the effective dimension and dimension distribution (which can be done analytically). The second method is to carry out a QMC error analysis on the quadratic approximation, establishing an explicit relationship between the QMC error and the PGM. Equalities and bounds on the QMC errors are established, in which the effect of the PGM is separated from the effect of the point set (in a similar way to the Koksma–Hlawka inequality). New measures for quantifying the accuracy of QMC methods combining with PGMs are introduced. The usefulness of the proposed methods is demonstrated on two typical high-dimensional finance problems, namely, the pricing of mortgage-backed securities and Asian options (with zero strike price). It is found that the success or failure of PGMs that do not take into account the underlying functions (such as the standard method, Brownian bridge and principal component analysis) strongly depends on the problem and the model parameters. On the other hand, the PGMs that take into account the underlying function are robust and powerful. The investigation presents new insight on PGMs and provides constructive guidance on the implementation and the design of new PGMs and new QMC rules. [Copyright &y& Elsevier]

Abstract: We prove that the set of all points of effective Hausdorff dimension 1 in is connected, and simultaneously that the complement of this set is not path-connected when . [Copyright &y& Elsevier]

Abstract: This paper presents new theoretical results to demonstrate that the referential dimensional decomposition (RDD) and cut-high-dimensional model representation (cut-HDMR), each developed independently and from a distinct perspective, lead to identical function approximations. Therefore, the reliability method stemming from the cut-HDMR approximation is precisely the same as the reliability method rooted in the RDD approximation. However, a second-moment error analysis finds neither the RDD approximation nor the cut-HDMR approximation to be optimal, whereas the approximation derived from the analysis-of-variance dimensional decomposition (ADD) results in minimum error for an arbitrary truncation. The expected errors from the RDD approximations are at least four to eight times larger than the errors from the ADD approximations. Therefore, further enhancements of decomposition-based reliability methods are possible by switching from RDD to ADD approximations. For both approximations, the decomposition can be truncated by an effective superposition dimension linked to respective approximation errors. [Copyright &y& Elsevier]

Abstract: We present a new general class of methods for the computation of high-dimensional integrals. The quadrature schemes result by truncation and discretization of the anchored-ANOVA decomposition. They are designed to exploit low effective dimensions and include sparse grid methods as special case. To derive bounds for the resulting modelling and discretization errors, we introduce effective dimensions for the anchored-ANOVA decomposition. We show that the new methods can be applied in locally adaptive and dimension-adaptive ways and demonstrate their efficiency by numerical experiments with high-dimensional integrals from finance. [Copyright &y& Elsevier]

High-dimension, low sample size (HDLSS) data are becoming common in various fields such as genetic microarrays, medical imaging, text recognition, finance, chemometrics, and so on. Such data have surprising and often counterintuitive geometric structures because of the high-dimensional noise that dominates and corrupts the local neighborhoods. In this article, we estimate the intrinsic dimension (ID) that allows one to distinguish between deterministic chaos and random noise of HDLSS data. A new ID estimating methodology is given and its properties are studied by using a d-asymptotic approach. [ABSTRACT FROM AUTHOR]

In this paper, we develop a simple and yet practically efficient algorithm for simulating high-dimensional exotic options. Our method is based on an extension of Imai and Tan's linear transformation method, which is originally proposed in the context of simulating a Gaussian process. By generalizing this method to other stochastic processes and exploiting the numerical inversion method of Hormann and Leydold, this method can be used to enhance quasi-Monte Carlo method in a wide range of applications. We demonstrate the relative efficiency of our proposed simulation technique using exotic option examples including Asian, lookback, barrier, and cliquet options for which the underlying asset price follows an exponential generalized hyperbolic Lévy process. We also illustrate the impact of our proposed method on dimension reduction. [ABSTRACT FROM AUTHOR]

We study constructive and resource-bounded scaled dimension as an information content measure and obtain several results that parallel previous work on unscaled dimension. Scaled dimension for finite strings is developed and shown to be closely related to Kolmogorov complexity. The scaled dimension of an infinite sequence is characterized by the scaled dimensions of its prefixes. We obtain an exact Kolmogorov complexity characterization of scaled dimension. Juedes and Lutz (Inf. Comput. 125(1), 13–31, ) established a small span theorem for P/poly-Turing reductions which asserts that for any problem A in ESPACE, either the class of problems reducible to A (the lower span) or the class of problems to which A is reducible (the upper span) has measure 0 in ESPACE. We apply our Kolmogorov complexity characterization to improve this to (−3)rd-order scaled dimension 0 in ESPACE. As a consequence we obtain a new upper bound on the Kolmogorov complexity of Turing-hard sets for ESPACE. [ABSTRACT FROM AUTHOR]

Abstract: We introduce a new measure notion on small complexity classes (called -measure), based on martingale families, that gets rid of some drawbacks of previous measure notions: it can be used to define dimension because martingale families can make money on all strings, and it yields random sequences with an equal frequency of ’s and ’s. On larger complexity classes ( and above), -measure is equivalent to Lutz resource-bounded measure. As applications to -measure, we answer a question raised in [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818] by improving their result to: for almost every language decidable in subexponential time, . We show that almost all languages in  do not have small non-uniform complexity. We compare -measure to previous notions and prove that martingale families are strictly stronger than -measure [E. Allender, M. Strauss, Measure on small complexity classes, with application for BPP, in: Proc. of the 35th Ann. IEEE Symp. on Found. of Comp. Sci., 1994, pp. 807–818], we also discuss the limitations of martingale families concerning finite unions. We observe that all classes closed under polynomial many-one reductions have measure zero in  iff they have measure zero in . We use martingale families to introduce a natural generalization of Lutz resource-bounded dimension [J.H. Lutz, Dimension in complexity classes, in: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000, pp. 158–169] on , which meets the intuition behind Lutz’s notion. We show that -dimension lies between finite-state dimension and dimension on . We prove an analogue of a Theorem of Eggleston in , i.e. the class of languages whose characteristic sequence contains ’s with frequency , has dimension the Shannon entropy of in . [Copyright &y& Elsevier]

Abstract: Quasi-Monte Carlo (QMC) methods have been playing an important role for high-dimensional problems in computational finance. Several techniques, such as the Brownian bridge (BB) and the principal component analysis, are often used in QMC as possible ways to improve the performance of QMC. This paper proposes a new BB construction, which enjoys some interesting properties that appear useful in QMC methods. The basic idea is to choose the new step of a Brownian path in a certain criterion such that it maximizes the variance explained by the new variable while holding all previously chosen steps fixed. It turns out that using this new construction, the first few variables are more “important” (in the sense of explained variance) than those in the ordinary BB construction, while the cost of the generation is still linear in dimension. We present empirical studies of the proposed algorithm for pricing high-dimensional Asian options and American options, and demonstrate the usefulness of the new BB. [Copyright &y& Elsevier]

Classical regression methods have focused mainly on estimating conditional mean functions. In recent years, however, quantile regression has emerged as a comprehensive approach to the statistical analysis of response models. In this article we consider the L1-norm (LASSO) regularized quantile regression (L1-norm QR), which uses the sum of the absolute values of the coefficients as the penalty. The L1-norm penalty has the advantage of simultaneously controlling the variance of the fitted coefficients and performing automatic variable selection. We propose an efficient algorithm that computes the entire solution path of the L1-norm QR. Furthermore, we derive an estimate for the effective dimension of the L1-norm QR model, which allows convenient selection of the regularization parameter. [ABSTRACT FROM AUTHOR]

The two most important notions of fractal dimension are Hausdorff dimension, developed by Hausdorff [Math. Ann., 79 (1919), pp. 157-179], and packing dimension, developed independently by Tricot [Math. Proc. Cambridge Philos. Soc., 91 (1982), pp. 57-74] and Sullivan [Acta Math., 153 (1984), pp. 259-277]. Both dimensions have the mathematical advantage of being defined from measures, and both have yielded extensive applications in fractal geometry and dynamical systems. Lutz [Proceedings of the 15th IEEE Conference on Computational Complexity, Florence, Italy, 2000, IEEE Computer Society Press, Piscataway, NJ, 2000, pp. 158-169] has recently proven a simple characterization of Hausdorff dimension in terms of gales, which are betting strategies that generalize martingales. Imposing various computability and complexity constraints on these gales produces a spectrum of effective versions of Hausdorff dimension, including constructive, computable, polynomial-space, polynomial-time, and finite-state dimensions. Work by several investigators has already used these effective dimensions to shed significant new light on a variety of topics in theoretical computer science. In this paper we show that packing dimension can also be characterized in terms of gales. Moreover, even though the usual definition of packing dimension is considerably more complex than that of Hausdorff dimension, our gale characterization of packing dimension is an exact dual of-and every bit as simple as-the gale characterization of Hausdorff dimension. Effectivizing our gale characterization of packing dimension produces a variety of effective strong dimensions, which are exact duals of the effective dimensions mentioned above. In general (and in analogy with the classical fractal dimensions), the effective strong dimension of a set or sequence is at least as great as its effective dimension, with equality for sets or sequences that are sufficiently regular. We develop the basic properties of effective strong dimensions and prove a number of results relating them to fundamental aspects of randomness, Kolmogorov complexity, prediction, Boolean circuit-size complexity, polynomial-time degrees, and data compression. Aside from the above characterization of packing dimension, our two main theorems are the following. 1. If →β = (β0, β1, …) is a computable sequence of biases that are bounded away from 0 and R is random with respect to →β, then the dimension and strong dimension of R are the lower and upper average entropies, respectively, of →β. 2. For each pair of Δ02 -computable real numbers 0 < α ⩽ β ⩽ 1, there exists A ϵ E such that the polynomial-time many-one degree of A has dimension α in E and strong dimension β in E. Our proofs of these theorems use a new large deviation theorem for self-information with respect to a bias sequence →β that need not be convergent. [ABSTRACT FROM AUTHOR]

Abstract: Two-dimensional lattices of points are connected with long-range links, whose lengths are distributed according to . By changing the decay exponent one can go from d-dimensional short-range networks to -dimensional networks topologically similar to random graphs. Percolation on these networks is numerically studied for systems of up to sites. The shortest-path, fractal and chemical dimensions are determined at the critical threshold, as a function of the decay exponent . [Copyright &y& Elsevier]

Abstract: Likelihood ratio tests of constant vs. monotone regression function, as well as linear vs. convex regression function and other tests with shape-restricted alternatives, are known to have null distributions equivalent to mixtures of beta random variates. The monotone and convex regression estimators are known to be inconsistent at the endpoints, where there is “spiking.” This spiking affects the critical values of the test statistic. Modified versions of the monotone and convex regression estimators are proposed that are consistent everywhere; when the modified versions are used in hypothesis testing, the null distribution is again an exact mixture of beta distributions, with different mixing parameters. Simulations show that the power of the test using the modified version is larger for the examples chosen. [Copyright &y& Elsevier]

Abstract: We consider high-dimensional integration in a broad class of functions where all elements have maximum effective dimension. We show that there exists an exact cubature with only two points. Therefore, not only the convergence but also the worst case error of quasi-Monte Carlo need not depend on the effective dimension at all. [Copyright &y& Elsevier]

Analysis of variance (ANOVA) is now often applied to functions defined on the unit cube, where it serves as a tool for the exploratory analysis of functions. The mean dimension of a function, defined as a natural weighted combination of its ANOVA mean squares, provides one measure of how hard or easy it is to integrate the function by quasi-Monte Carlo sampling. This article presents some new identities relating the mean dimension, and some analogously defined higher moments, to the variance importance measures of I. M. Sobol. As a result, we are able to measure the mean dimension of certain functions arising in computational finance. We produce an unbiased and nonnegative estimate of the variance contribution of the highest-order interaction that avoids the cancellation problems of previous estimates. In an application to extreme value theory, we find that, among other things, the minimum of d independent U[0, 1] random variables has a mean dimension of 2(d + 1)/(d +3). [ABSTRACT FROM AUTHOR]

Abstract: The urban road networks of the 20 largest German cities have been analysed, based on a detailed database providing the geographical positions as well as the travel-times for network sizes up to 37,000 nodes and 87,000 links. As the human driver recognises travel-times rather than distances, faster roads appear to be ‘shorter’ than slower ones. The resulting metric space has an effective dimension , which is a significant measure of the heterogeneity of road speeds. We found that traffic strongly concentrates on only a small fraction of the roads. The distribution of vehicular flows over the roads obeys a power law, indicating a clear hierarchical order of the roads. Studying the cellular structure of the areas enclosed by the roads, the distribution of cell sizes is scale invariant as well. [Copyright &y& Elsevier]

Abstract: One- and two-dimensional lattices of points are connected with long-range links, whose lengths are distributed according to . By changing the decay exponent one can go from d-dimensional short-range networks to -dimensional networks topologically similar to random graphs. An effective dimension can be defined in terms of the shortest-path properties of these networks. These effective dimensions are calculated here in one and two dimensions, for system sizes of up to points. [Copyright &y& Elsevier]

Abstract: We introduce a class of functions in high dimensions which have the maximum effective dimension, then prove that generalized Sobol’ sequences provide the convergence rate for the integration of this class of functions. An important consequence is that high-dimensional problems for which quasi-Monte Carlo outperforms Monte Carlo are not necessarily of low-effective dimension. [Copyright &y& Elsevier]

Many problems in mathematical finance can be formulated as high-dimensional integrals, where the large number of dimensions arises from small time steps in time discretization and/or a large number of state variables. Quasi--Monte Carlo (QMC) methods have been successfully used for approximating such integrals. To understand this success, this paper focuses on investigating the special features of some typical high-dimensional finance problems, namely, option pricing and bond valuation. We provide new insight into the connection between the effective dimension and the efficiency of QMC, and we present methods to analyze the dimension structure of a function. We confirm the observation of Caflisch, Morokoff, and Owen that functions from finance are often of low effective dimension, in the sense that they can be well approximated by their low-order ANOVA (analysis of variance) terms, usually just the order-1 and order-2 terms. We explore why the effective dimension is small for many integrals from finance. By deriving explicit forms of the ANOVA terms in simple cases, we find that the importance of each dimension is naturally weighted by certain hidden weights. These weights characterize the relative importance of different variables or groups of variables and limit the importance of the higher-order ANOVA terms. We study the variance ratios captured by low-order ANOVA terms and their asymptotic properties as the dimension tends to infinity, and we show that with the increase of dimension the lower-order terms continue to play a significant role and the higher-order terms tend to be negligible. This provides some insight into high-dimensional problems from finance and explains why QMC algorithms are efficient for problems of this kind. [ABSTRACT FROM AUTHOR]

The renormalization group (RG) approach is a powerful theoretical framework, more suitable for upscaling strong heterogeneity than low-order perturbation expansions. Applications of RG methods in subsurface hydrology include the calculation of (1) macroscopic transport parameters such as effective and equivalent hydraulic conductivity and dispersion coefficients, and (2) anomalous exponents characterizing the dispersion of contaminants due to long-range conductivity correlations or broad (heavy-tailed) distributions of the groundwater velocity. First, we review the main ideas of RG methods and their hydrological applications. Then, we focus on the hydraulic conductivity in saturated porous media with isotropic lognormal heterogeneity, and we present an RG calculation based on the replica method. The RG analysis gives rigorous support to the exponential conjecture for the effective hydraulic conductivity [Water Resour. Res. 19 (1) (1983) 161]. Using numerical simulations in two dimensions with a bimodal conductivity distribution, we demonstrate that the exponential expression is not suitable for all types of heterogeneity. We also introduce an RG coarse-grained conductivity and investigate its applications in estimating the conductivity of blocks or flow domains with finite size. Finally, we define the fractional effective dimension, and we show that it justifies fractal exponents in the range 1−2/d&les;α<1 (where d is the actual medium dimension) in the geostatistical power average. [Copyright &y& Elsevier]

Quasi-Monte Carlo (QMC) methods are successfully used for high-dimensional integrals arising in many applications. To understand this success, the notion of effective dimension has been introduced. In this paper, we analyse certain function classes commonly used in QMC methods for empirical and theoretical investigations and show that the problem of determining their effective dimension is analytically tractable. For arbitrary square integrable functions, we propose a numerical algorithm to compute their truncation dimension. We also consider some realistic problems from finance: the pricing of options. We study the special structure of the corresponding integrands by determining their effective dimension and show how large the effective dimension can be reduced and how much the accuracy of QMC estimates can be improved by using the Brownian bridge and the principal component analysis techniques. A critical discussion of the influence of these techniques on the QMC error is presented. The connection between the effective dimension and the performance of QMC methods is demonstrated by examples. [Copyright &y& Elsevier]

An unbiased test for the appropriateness of the simple linear regression model is presented. The null hypothesis is that the underlying regression function is indeed a line, and the alternative is that it is convex. The exact distribution for a likelihood ratio test statistic is that of a mixture of beta random variables, with the mixing distribution calculated from relative volumes of polyhedral convex cones determined by the convex shape restriction. Simulations show that the power of the test is favourable compared with the usual F‐test against a quadratic model, for some nonquadratic choices of the underlying regression function. [ABSTRACT FROM PUBLISHER]

We use Kolmogorov complexity methods to give a lower bound on the effective Hausdorff dimension of the point (x , a x + b) , given real numbers a , b , and x. We apply our main theorem to a problem in fractal geometry, giving an improved lower bound on the (classical) Hausdorff dimension of generalized sets of Furstenberg type. [ABSTRACT FROM AUTHOR]