In this paper, we propose an offline-online strategy based on the Localized Orthogonal Decomposition (LOD) method for elliptic multiscale problems with randomly perturbed diffusion coefficient. We consider a periodic deterministic coefficient with local defects that occur with probability $p$. The offline phase pre-computes entries to global LOD stiffness matrices on a single reference element (exploiting the periodicity) for a selection of defect configurations. Given a sample of the perturbed diffusion the corresponding LOD stiffness matrix is then computed by taking linear combinations of the pre-computed entries, in the online phase. Our computable error estimates show that this yields a good coarse-scale approximation of the solution for small $p$, which is illustrated by extensive numerical experiments. This makes the proposed technique attractive already for moderate sample sizes in a Monte Carlo simulation.
We present a novel hybrid strategy based on machine learning to improve curvature estimation in the level-set method. The proposed inference system couples enhanced neural networks with standard numerical schemes to compute curvature more accurately. The core of our hybrid framework is a switching mechanism that relies on well established numerical techniques to gauge curvature. If the curvature magnitude is larger than a resolution-dependent threshold, it uses a neural network to yield a better approximation. Our networks are multilayer perceptrons fitted to synthetic data sets composed of sinusoidal- and circular-interface samples at various configurations. To reduce data set size and training complexity, we leverage the problem's characteristic symmetry and build our models on just half of the curvature spectrum. These savings lead to a powerful inference system able to outperform any of its numerical or neural component alone. Experiments with stationary, smooth interfaces show that our hybrid solver is notably superior to conventional numerical methods in coarse grids and along steep interface regions. Compared to prior research, we have observed outstanding gains in precision after training the regression model with data pairs from more than a single interface type and transforming data with specialized input preprocessing. In particular, our findings confirm that machine learning is a promising venue for reducing or removing mass loss in the level-set method.
Semidefinite programming (SDP) is a powerful tool for tackling a wide range of computationally hard problems such as clustering. Despite the high accuracy, semidefinite programs are often too slow in practice with poor scalability on large (or even moderate) datasets. In this paper, we introduce a linear time complexity algorithm for approximating an SDP relaxed $K$-means clustering. The proposed sketch-and-lift (SL) approach solves an SDP on a subsampled dataset and then propagates the solution to all data points by a nearest-centroid rounding procedure. It is shown that the SL approach enjoys a similar exact recovery threshold as the $K$-means SDP on the full dataset, which is known to be information-theoretically tight under the Gaussian mixture model. The SL method can be made adaptive with enhanced theoretic properties when the cluster sizes are unbalanced. Our simulation experiments demonstrate that the statistical accuracy of the proposed method outperforms state-of-the-art fast clustering algorithms without sacrificing too much computational efficiency, and is comparable to the original $K$-means SDP with substantially reduced runtime.
In presenting an irrigation detection methodology that leverages multiscale satellite imagery of vegetation abundance, this paper introduces a process to supplement limited ground-collected labels and ensure classifier applicability in an area of interest. Spatiotemporal analysis of MODIS 250m Enhanced Vegetation Index (EVI) timeseries characterizes native vegetation phenologies at regional scale to provide the basis for a continuous phenology map that guides supplementary label collection over irrigated and non-irrigated agriculture. Subsequently, validated dry season greening and senescence cycles observed in 10m Sentinel-2 imagery are used to train a suite of classifiers for automated detection of potential smallholder irrigation. Strategies to improve model robustness are demonstrated, including a method of data augmentation that randomly shifts training samples; and an assessment of classifier types that produce the best performance in withheld target regions. The methodology is applied to detect smallholder irrigation in two states in the Ethiopian highlands, Tigray and Amhara. Results show that a transformer-based neural network architecture allows for the most robust prediction performance in withheld regions, followed closely by a CatBoost random forest model. Over withheld ground-collection survey labels, the transformer-based model achieves 96.7% accuracy over non-irrigated samples and 95.9% accuracy over irrigated samples. Over a larger set of samples independently collected via the introduced method of label supplementation, non-irrigated and irrigated labels are predicted with 98.3% and 95.5% accuracy, respectively. The detection model is then deployed over Tigray and Amhara, revealing crop rotation patterns and year-over-year irrigated area change. Predictions suggest that irrigated area in these two states has decreased by approximately 40% from 2020 to 2021.
We consider decentralized machine learning over a network where the training data is distributed across $n$ agents, each of which can compute stochastic model updates on their local data. The agent's common goal is to find a model that minimizes the average of all local loss functions. While gradient tracking (GT) algorithms can overcome a key challenge, namely accounting for differences between workers' local data distributions, the known convergence rates for GT algorithms are not optimal with respect to their dependence on the mixing parameter $p$ (related to the spectral gap of the connectivity matrix). We provide a tighter analysis of the GT method in the stochastic strongly convex, convex and non-convex settings. We improve the dependency on $p$ from $\mathcal{O}(p^{-2})$ to $\mathcal{O}(p^{-1}c^{-1})$ in the noiseless case and from $\mathcal{O}(p^{-3/2})$ to $\mathcal{O}(p^{-1/2}c^{-1})$ in the general stochastic case, where $c \geq p$ is related to the negative eigenvalues of the connectivity matrix (and is a constant in most practical applications). This improvement was possible due to a new proof technique which could be of independent interest.
In this work, a multirate in time approach resolving the different time scales of a convection-dominated transport and coupled fluid flow is developed and studied in view of goal-oriented error control by means of the Dual Weighted Residual (DWR) method. Key ingredients are an arbitrary degree discontinuous Galerkin time discretization of the underlying subproblems, an a posteriori error representation for the transport problem coupled with flow and its implementation using space-time tensor-product spaces. The error representation allows the separation of the temporal and spatial discretization error which serve as local error indicators for adaptive mesh refinement. The performance of the approach and its software implementation are studied by numerical convergence examples as well as an example of physical interest for convection-dominated transport.
Random Ferns -- as a less known example of Ensemble Learning -- have been successfully applied in many Computer Vision applications ranging from keypoint matching to object detection. This paper extends the Random Fern framework to the semantic segmentation of polarimetric synthetic aperture radar images. By using internal projections that are defined over the space of Hermitian matrices, the proposed classifier can be directly applied to the polarimetric covariance matrices without the need to explicitly compute predefined image features. Furthermore, two distinct optimization strategies are proposed: The first based on pre-selection and grouping of internal binary features before the creation of the classifier; and the second based on iteratively improving the properties of a given Random Fern. Both strategies are able to boost the performance by filtering features that are either redundant or have a low information content and by grouping correlated features to best fulfill the independence assumptions made by the Random Fern classifier. Experiments show that results can be achieved that are similar to a more complex Random Forest model and competitive to a deep learning baseline.
For $d\in\mathbb{N}$, let $S$ be a set of points in $\mathbb{R}^d$ in general position. A set $I$ of $k$ points from $S$ is a $k$-island in $S$ if the convex hull $\mathrm{conv}(I)$ of $I$ satisfies $\mathrm{conv}(I) \cap S = I$. A $k$-island in $S$ in convex position is a $k$-hole in $S$. For $d,k\in\mathbb{N}$ and a convex body $K\subseteq\mathbb{R}^d$ of volume $1$, let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$. We show that the expected number of $k$-holes in $S$ is in $O(n^d)$. Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in $S$ by $2^{d-1}\cdot d!\cdot\binom{n}{d}$. This is tight in the plane up to a lower-order term. Our method gives an asymptotically tight upper bound $O(n^d)$ even in the much more general setting, where we estimate the expected number of $k$-islands in $S$.
Solving analytically intractable partial differential equations (PDEs) that involve at least one variable defined in an unbounded domain requires efficient numerical methods that accurately resolve the dependence of the PDE on that variable over several orders of magnitude. Unbounded domain problems arise in various application areas and solving such problems is important for understanding multi-scale biological dynamics, resolving physical processes at long time scales and distances, and performing parameter inference in engineering problems. In this work, we combine two classes of numerical methods: (i) physics-informed neural networks (PINNs) and (ii) adaptive spectral methods. The numerical methods that we develop take advantage of the ability of physics-informed neural networks to easily implement high-order numerical schemes to efficiently solve PDEs. We then show how recently introduced adaptive techniques for spectral methods can be integrated into PINN-based PDE solvers to obtain numerical solutions of unbounded domain problems that cannot be efficiently approximated by standard PINNs. Through a number of examples, we demonstrate the advantages of the proposed spectrally adapted PINNs (s-PINNs) over standard PINNs in approximating functions, solving PDEs, and estimating model parameters from noisy observations in unbounded domains.
In this paper we propose and validate a multiscale model for the description of particle diffusion in presence of trapping boundaries. We start from a drift-diffusion equation in which the drift term describes the effect of bubble traps, and is modeled by a short range potential with an attractive term and a repulsive core. The interaction of the particles attracted by the bubble surface is simulated by the Lennard-Jones potential that simplifies the capture due to the hydrophobic properties of the ions. In our model the effect of the potential is replaced by a suitable boundary condition derived by mass conservation and asymptotic analysis. The potential is assumed to have a range of small size $\varepsilon$. An asymptotic expansion in the $\varepsilon$ is considered, and the boundary conditions are obtained by retaining the lowest order terms in the expansion. Another aspect we investigate is saturation effect coming from high concentrations in the proximity of the bubble surface. Various studies show that these reactions lead to a modification of the model, including also non linear terms. The validity of the model is carefully checked with several tests in 1D, 2D and different geometries.
In this work, we consider the distributed optimization of non-smooth convex functions using a network of computing units. We investigate this problem under two regularity assumptions: (1) the Lipschitz continuity of the global objective function, and (2) the Lipschitz continuity of local individual functions. Under the local regularity assumption, we provide the first optimal first-order decentralized algorithm called multi-step primal-dual (MSPD) and its corresponding optimal convergence rate. A notable aspect of this result is that, for non-smooth functions, while the dominant term of the error is in $O(1/\sqrt{t})$, the structure of the communication network only impacts a second-order term in $O(1/t)$, where $t$ is time. In other words, the error due to limits in communication resources decreases at a fast rate even in the case of non-strongly-convex objective functions. Under the global regularity assumption, we provide a simple yet efficient algorithm called distributed randomized smoothing (DRS) based on a local smoothing of the objective function, and show that DRS is within a $d^{1/4}$ multiplicative factor of the optimal convergence rate, where $d$ is the underlying dimension.