We formulate the quadratic eigenvalue problem underlying the mathematical model of a linear vibrational system as an eigenvalue problem of a diagonal-plus-low-rank matrix $A$. The eigenvector matrix of $A$ has a Cauchy-like structure. Optimal viscosities are those for which $trace(X)$ is minimal, where $X$ is the solution of the Lyapunov equation $AX+XA^{*}=GG^{*}$. Here $G$ is a low-rank matrix which depends on the eigenfrequencies that need to be damped. After initial eigenvalue decomposition of linearized problem which requires $O(n^3)$ operations, our algorithm computes optimal viscosities for each choice of external dampers in $O(n^2)$ operations, provided that the number of dampers is small. Hence, the subsequent optimization is order of magnitude faster than in the standard approach which solves Lyapunov equation in each step, thus requiring $O(n^3)$ operations. Our algorithm is based on $O(n^2)$ eigensolver for complex symmetric diagonal-plus-rank-one matrices and fast $O(n^2)$ multiplication of linked Cauchy-like matrices.
相關內容
Nonstationary Gaussian process models can capture complex spatially varying dependence structures in spatial datasets. However, the large number of observations in modern datasets makes fitting such models computationally intractable with conventional dense linear algebra. In addition, derivative-free or even first-order optimization methods can be slow to converge when estimating many spatially varying parameters. We present here a computational framework that couples an algebraic block-diagonal plus low-rank covariance matrix approximation with stochastic trace estimation to facilitate the efficient use of second-order solvers for maximum likelihood estimation of Gaussian process models with many parameters. We demonstrate the effectiveness of these methods by simultaneously fitting 192 parameters in the popular nonstationary model of Paciorek and Schervish using 107,600 sea surface temperature anomaly measurements.
We are interested in obtaining approximate solutions to parameterized linear systems of the form $A(\mu) x(\mu) = b$ for many values of the parameter $\mu$. Here $A(\mu)$ is large, sparse, and nonsingular, with a nonlinear analytic dependence on $\mu$. Our approach is based on a companion linearization for parameterized linear systems. The companion matrix is similar to the operator in the infinite Arnoldi method, and we use this to adapt the flexible GMRES setting. In this way, our method returns a function $\tilde{x}(\mu)$ which is cheap to evaluate for different $\mu$, and the preconditioner is applied only approximately. This novel approach leads to increased freedom to carry out the action of the operation inexactly, which provides performance improvement over the method infinite GMRES, without a loss of accuracy in general. We show that the error of our method is estimated based on the magnitude of the parameter $\mu$, the inexactness of the preconditioning, and the spectrum of the linear companion matrix. Numerical examples from a finite element discretization of a Helmholtz equation with a parameterized material coefficient illustrate the competitiveness of our approach. The simulations are reproducible and publicly available online.
We present a data-driven approach to characterizing nonidentifiability of a model's parameters and illustrate it through dynamic as well as steady kinetic models. By employing Diffusion Maps and their extensions, we discover the minimal combinations of parameters required to characterize the output behavior of a chemical system: a set of effective parameters for the model. Furthermore, we introduce and use a Conformal Autoencoder Neural Network technique, as well as a kernel-based Jointly Smooth Function technique, to disentangle the redundant parameter combinations that do not affect the output behavior from the ones that do. We discuss the interpretability of our data-driven effective parameters, and demonstrate the utility of the approach both for behavior prediction and parameter estimation. In the latter task, it becomes important to describe level sets in parameter space that are consistent with a particular output behavior. We validate our approach on a model of multisite phosphorylation, where a reduced set of effective parameters (nonlinear combinations of the physical ones) has previously been established analytically.
Whilst lattice-based cryptosystems are believed to be resistant to quantum attack, they are often forced to pay for that security with inefficiencies in implementation. This problem is overcome by ring- and module-based schemes such as Ring-LWE or Module-LWE, whose keysize can be reduced by exploiting its algebraic structure, allowing for faster computations. Many rings may be chosen to define such cryptoschemes, but cyclotomic rings, due to their cyclic nature allowing for easy multiplication, are the community standard. However, there is still much uncertainty as to whether this structure may be exploited to an adversary's benefit. In this paper, we show that the decomposition group of a cyclotomic ring of arbitrary conductor can be utilised to significantly decrease the dimension of the ideal (or module) lattice required to solve a given instance of SVP. Moreover, we show that there exist a large number of rational primes for which, if the prime ideal factors of an ideal lie over primes of this form, give rise to an "easy" instance of SVP. It is important to note that the work on ideal SVP does not break Ring-LWE, since its security reduction is from worst case ideal SVP to average case Ring-LWE, and is one way.
Age of information (AoI) is an effective performance metric measuring the freshness of information and is popular for applications involving status update. Most of the existing works have adopted average AoI as the metric, which cannot provide strict performance guarantees. In this work, the outage probability of the peak AoI exceeding a given threshold is analyzed in a multi-source system under round robin scheduling. Two queueing disciplines are considered, namely the first-come-first-serve (FCFS) queue and the single packet queue. For FCFS, upper and lower bounds on the outage probability are derived which coincides asymptotically, characterizing its true scaling. For the single packet queue, an upper bound is derived whose effectiveness is validated by the simulation results. The analysis concretizes the common belief that single packet queueing has a better AoI performance than FCFS. Moreover, it also reveals that the two disciplines would have similar asymptotic performance when the inter-arrival time is much larger than the total transmission time.
Modern neural networks are often operated in a strongly overparametrized regime: they comprise so many parameters that they can interpolate the training set, even if actual labels are replaced by purely random ones. Despite this, they achieve good prediction error on unseen data: interpolating the training set does not lead to a large generalization error. Further, overparametrization appears to be beneficial in that it simplifies the optimization landscape. Here we study these phenomena in the context of two-layers neural networks in the neural tangent (NT) regime. We consider a simple data model, with isotropic covariates vectors in $d$ dimensions, and $N$ hidden neurons. We assume that both the sample size $n$ and the dimension $d$ are large, and they are polynomially related. Our first main result is a characterization of the eigenstructure of the empirical NT kernel in the overparametrized regime $Nd\gg n$. This characterization implies as a corollary that the minimum eigenvalue of the empirical NT kernel is bounded away from zero as soon as $Nd\gg n$, and therefore the network can exactly interpolate arbitrary labels in the same regime. Our second main result is a characterization of the generalization error of NT ridge regression including, as a special case, min-$\ell_2$ norm interpolation. We prove that, as soon as $Nd\gg n$, the test error is well approximated by the one of kernel ridge regression with respect to the infinite-width kernel. The latter is in turn well approximated by the error of polynomial ridge regression, whereby the regularization parameter is increased by a `self-induced' term related to the high-degree components of the activation function. The polynomial degree depends on the sample size and the dimension (in particular on $\log n/\log d$).
We study the family of functions that are represented by a linear convolutional neural network (LCN). These functions form a semi-algebraic subset of the set of linear maps from input space to output space. In contrast, the families of functions represented by fully-connected linear networks form algebraic sets. We observe that the functions represented by LCNs can be identified with polynomials that admit certain factorizations, and we use this perspective to describe the impact of the network's architecture on the geometry of the resulting function space. We further study the optimization of an objective function over an LCN, analyzing critical points in function space and in parameter space, and describing dynamical invariants for gradient descent. Overall, our theory predicts that the optimized parameters of an LCN will often correspond to repeated filters across layers, or filters that can be decomposed as repeated filters. We also conduct numerical and symbolic experiments that illustrate our results and present an in-depth analysis of the landscape for small architectures.
In this paper, we give pointwise estimates of a Vorono\"i-based finite volume approximation of the Laplace-Beltrami operator on Vorono\"i-Delaunay decompositions of the sphere. These estimates are the basis for a local error analysis, in the maximum norm, of the approximate solution of the Poisson equation and its gradient. Here, we consider the Vorono\"i-based finite volume method as a perturbation of the finite element method. Finally, using regularized Green's functions, we derive quasi-optimal convergence order in the maximum-norm with minimal regularity requirements. Numerical examples show that the convergence is at least as good as predicted.
Much of the literature on optimal design of bandit algorithms is based on minimization of expected regret. It is well known that designs that are optimal over certain exponential families can achieve expected regret that grows logarithmically in the number of arm plays, at a rate governed by the Lai-Robbins lower bound. In this paper, we show that when one uses such optimized designs, the regret distribution of the associated algorithms necessarily has a very heavy tail, specifically, that of a truncated Cauchy distribution. Furthermore, for $p>1$, the $p$'th moment of the regret distribution grows much faster than poly-logarithmically, in particular as a power of the total number of arm plays. We show that optimized UCB bandit designs are also fragile in an additional sense, namely when the problem is even slightly mis-specified, the regret can grow much faster than the conventional theory suggests. Our arguments are based on standard change-of-measure ideas, and indicate that the most likely way that regret becomes larger than expected is when the optimal arm returns below-average rewards in the first few arm plays, thereby causing the algorithm to believe that the arm is sub-optimal. To alleviate the fragility issues exposed, we show that UCB algorithms can be modified so as to ensure a desired degree of robustness to mis-specification. In doing so, we also provide a sharp trade-off between the amount of UCB exploration and the tail exponent of the resulting regret distribution.
We provide a unifying framework for $\mathcal{L}_2$-optimal reduced-order modeling for linear time-invariant dynamical systems and stationary parametric problems. Using parameter-separable forms of the reduced-model quantities, we derive the gradients of the $\mathcal{L}_2$ cost function with respect to the reduced matrices, which then allows a non-intrusive, data-driven, gradient-based descent algorithm to construct the optimal approximant using only output samples. By choosing an appropriate measure, the framework covers both continuous (Lebesgue) and discrete cost functions. We show the efficacy of the proposed algorithm via various numerical examples. Furthermore, we analyze under what conditions the data-driven approximant can be obtained via projection.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191