This paper proposes several approaches as baselines to compute a shared active subspace for multivariate vector-valued functions. The goal is to minimize the deviation between the function evaluations on the original space and those on the reconstructed one. This is done either by manipulating the gradients or the symmetric positive (semi-)definite (SPD) matrices computed from the gradients of each component function so as to get a single structure common to all component functions. These approaches can be applied to any data irrespective of the underlying distribution unlike the existing vector-valued approach that is constrained to a normal distribution. We test the effectiveness of these methods on five optimization problems. The experiments show that, in general, the SPD-level methods are superior to the gradient-level ones, and are close to the vector-valued approach in the case of a normal distribution. Interestingly, in most cases it suffices to take the sum of the SPD matrices to identify the best shared active subspace.
This paper considers both the least squares and quasi-maximum likelihood estimation for the recently proposed scalable ARMA model, a parametric infinite-order vector AR model, and their asymptotic normality is also established. It makes feasible the inference on this computationally efficient model, especially for financial time series. An efficient block coordinate descent algorithm is further introduced to search for estimates, and a Bayesian information criterion is suggested for model selection. Simulation experiments are conducted to illustrate their finite sample performance, and a real application on six macroeconomic indicators illustrates the usefulness of the proposed methodology.
In this work, we address parametric non-stationary fluid dynamics problems within a model order reduction setting based on domain decomposition. Starting from the optimisation-based domain decomposition approach, we derive an optimal control problem, for which we present a convergence analysis in the case of non-stationary incompressible Navier-Stokes equations. We discretize the problem with the finite element method and we compare different model order reduction techniques: POD-Galerkin and a non-intrusive neural network procedure. We show that the classical POD-Galerkin is more robust and accurate also in transient areas, while the neural network can obtain simulations very quickly though being less precise in the presence of discontinuities in time or parameter domain. We test the proposed methodologies on two fluid dynamics benchmarks with physical parameters and time dependency: the non-stationary backward-facing step and lid-driven cavity flow.
Modern regression applications can involve hundreds or thousands of variables which motivates the use of variable selection methods. Bayesian variable selection defines a posterior distribution on the possible subsets of the variables (which are usually termed models) to express uncertainty about which variables are strongly linked to the response. This can be used to provide Bayesian model averaged predictions or inference, and to understand the relative importance of different variables. However, there has been little work on meaningful representations of this uncertainty beyond first order summaries. We introduce Cartesian credible sets to address this gap. The elements of these sets are formed by concatenating sub-models defined on each block of a partition of the variables. Investigating these sub-models allow us to understand whether the models in the Cartesian credible set always/never/sometimes include a particular variable or group of variables and provide a useful summary of model uncertainty. We introduce methods to find these sets that emphasize ease of understanding. The potential of the method is illustrated on regression problems with both small and large numbers of variables.
Motivated by a recent work on a preconditioned MINRES for flipped linear systems in imaging, in this note we extend the scope of that research for including more precise boundary conditions such as reflective and anti-reflective ones. We prove spectral results for the matrix-sequences associated to the original problem, which justify the use of the MINRES in the current setting. The theoretical spectral analysis is supported by a wide variety of numerical experiments, concerning the visualization of the spectra of the original matrices in various ways. We also report numerical tests regarding the convergence speed and regularization features of the associated GMRES and MINRES methods. Conclusions and open problems end the present study.
The main reason for query model's prominence in complexity theory and quantum computing is the presence of concrete lower bounding techniques: polynomial and adversary method. There have been considerable efforts to give lower bounds using these methods, and to compare/relate them with other measures based on the decision tree. We explore the value of these lower bounds on quantum query complexity and their relation with other decision tree based complexity measures for the class of symmetric functions, arguably one of the most natural and basic sets of Boolean functions. We show an explicit construction for the dual of the positive adversary method and also of the square root of private coin certificate game complexity for any total symmetric function. This shows that the two values can't be distinguished for any symmetric function. Additionally, we show that the recently introduced measure of spectral sensitivity gives the same value as both positive adversary and approximate degree for every total symmetric Boolean function. Further, we look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. Finally, we study how large certificate complexity and block sensitivity can be as compared to sensitivity for symmetric functions (even up to constant factors). We show tight separations, i.e., give upper bounds on possible separations and construct functions achieving the same.
Boundary value problems involving elliptic PDEs such as the Laplace and the Helmholtz equations are ubiquitous in mathematical physics and engineering. Many such problems can be alternatively formulated as integral equations that are mathematically more tractable. However, an integral-equation formulation poses a significant computational challenge: solving large dense linear systems that arise upon discretization. In cases where iterative methods converge rapidly, existing methods that draw on fast summation schemes such as the Fast Multipole Method are highly efficient and well-established. More recently, linear complexity direct solvers that sidestep convergence issues by directly computing an invertible factorization have been developed. However, storage and computation costs are high, which limits their ability to solve large-scale problems in practice. In this work, we introduce a distributed-memory parallel algorithm based on an existing direct solver named ``strong recursive skeletonization factorization.'' Specifically, we apply low-rank compression to certain off-diagonal matrix blocks in a way that minimizes computation and data movement. Compared to iterative algorithms, our method is particularly suitable for problems involving ill-conditioned matrices or multiple right-hand sides. Large-scale numerical experiments are presented to show the performance of our Julia implementation.
Binary field extensions are fundamental to many applications, such as multivariate public key cryptography, code-based cryptography, and error-correcting codes. Their implementation requires a foundation in number theory and algebraic geometry and necessitates the utilization of efficient bases. The continuous increase in the power of computation, and the design of new (quantum) computers increase the threat to the security of systems and impose increasingly demanding encryption standards with huge polynomial or extension degrees. For cryptographic purposes or other common implementations of finite fields arithmetic, it is essential to explore a wide range of implementations with diverse bases. Unlike some bases, polynomial and Gaussian normal bases are well-documented and widely employed. In this paper, we explore other forms of bases of $\mathbb{F}_{2^n}$ over $\mathbb{F}_2$ to demonstrate efficient implementation of operations within different ranges. To achieve this, we leverage results on fast computations and elliptic periods introduced by Couveignes and Lercier, and subsequently expanded upon by Ezome and Sall. This leads to the establishment of new tables for efficient computation over binary fields.
This paper focuses on a semiparametric regression model in which the response variable is explained by the sum of two components. One of them is parametric (linear), the corresponding explanatory variable is measured with additive error and its dimension is finite ($p$). The other component models, in a nonparametric way, the effect of a functional variable (infinite dimension) on the response. $k$-NN based estimators are proposed for each component, and some asymptotic results are obtained. A simulation study illustrates the behaviour of such estimators for finite sample sizes, while an application to real data shows the usefulness of our proposal.
We provide full theoretical guarantees for the convergence behaviour of diffusion-based generative models under the assumption of strongly log-concave data distributions while our approximating class of functions used for score estimation is made of Lipschitz continuous functions. We demonstrate via a motivating example, sampling from a Gaussian distribution with unknown mean, the powerfulness of our approach. In this case, explicit estimates are provided for the associated optimization problem, i.e. score approximation, while these are combined with the corresponding sampling estimates. As a result, we obtain the best known upper bound estimates in terms of key quantities of interest, such as the dimension and rates of convergence, for the Wasserstein-2 distance between the data distribution (Gaussian with unknown mean) and our sampling algorithm. Beyond the motivating example and in order to allow for the use of a diverse range of stochastic optimizers, we present our results using an $L^2$-accurate score estimation assumption, which crucially is formed under an expectation with respect to the stochastic optimizer and our novel auxiliary process that uses only known information. This approach yields the best known convergence rate for our sampling algorithm.
In this contribution we apply an adaptive model hierarchy, consisting of a full-order model, a reduced basis reduced order model, and a machine learning surrogate, to parametrized linear-quadratic optimal control problems. The involved reduced order models are constructed adaptively and are called in such a way that the model hierarchy returns an approximate solution of given accuracy for every parameter value. At the same time, the fastest model of the hierarchy is evaluated whenever possible and slower models are only queried if the faster ones are not sufficiently accurate. The performance of the model hierarchy is studied for a parametrized heat equation example with boundary value control.