Search

Recently, in a series of papers [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672; C. Wang, M. Tao, J. Nagy, and Y. Lou, SIAM J. Imaging Sci., 14 (2021), pp. 749-777; C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669; P. Yin, E. Esser, and J. Xin, Commun. Inf. Syst., 14 (2014), pp. 87-109], the ratio of ℓ1 and ℓ2 norms was proposed as a sparsity inducing function for noiseless compressed sensing. In this paper, we further study properties of such model in the noiseless setting, and propose an algorithm for minimizing ℓ1/ℓ2 subject to noise in the measurements. Specifically, we show that the extended objective function (the sum of the objective and the indicator function of the constraint set) of the model in [Y. Rahimi, C. Wang, H. Dong, and Y. Lou, SIAM J. Sci. Comput., 41 (2019), pp. A3649-A3672] satisfies the Kurdyka--Lojasiewicz (KL) property with exponent 1/2; this allows us to establish linear convergence of the algorithm proposed in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) under mild assumptions. We next extend the ℓ1/ℓ2 model to handle compressed sensing problems with noise. We establish the solution existence for some of these models under the spherical section property [S. A. Vavasis, Derivation of Compressive Sensing Theorems from the Spherical Section Property, University of Waterloo, 2009; Y. Zhang, J. Oper. Res. Soc. China, 1 (2013), pp. 79-105] and extend the algorithm in [C. Wang, M. Yan, and Y. Lou, IEEE Trans. Signal Process., 68 (2020), pp. 2660-2669] (see equation 11) by incorporating moving-balls-approximation techniques [A. Auslender, R. Shefi, and M. Teboulle, SIAM J. Optim., 20 (2010), pp. 3232-3259] for solving these problems. We prove the subsequential convergence of our algorithm under mild conditions and establish global convergence of the whole sequence generated by our algorithm by imposing additional KL and differentiability assumptions on a specially constructed potential function. Finally, we perform numerical experiments on robust compressed sensing and basis pursuit denoising with residual error measured by \ell 2 norm or Lorentzian norm via solving the corresponding ℓ1/ℓ2 models by our algorithm. Our numerical simulations show that our algorithm is able to recover the original sparse vectors with reasonable accuracy. [ABSTRACT FROM AUTHOR]

This paper develops a novel limited-memory method to solve dynamic optimization problems. The memory requirements for such problems often present a major obstacle, particularly for problems with PDE constraints such as optimal flow control, full waveform inversion, and optical tomography. In these problems, PDE constraints uniquely determine the state of a physical system for a given control; the goal is to find the value of the control that minimizes an objective. While the control is often low dimensional, the state is typically more expensive to store. This paper suggests using randomized matrix approximation to compress the state as it is generated and shows how to use the compressed state to reliably solve the original dynamic optimization problem. Concretely, the compressed state is used to compute approximate gradients and to apply the Hessian to vectors. The approximation error in these quantities is controlled by the target rank of the sketch. This approximate first- and second-order information can readily be used in any optimization algorithm. As an example, we develop a sketched trust-region method that adaptively chooses the target rank using a posteriori error information and provably converges to a stationary point of the original problem. Numerical experiments with the sketched trust-region method show promising performance on challenging problems such as the optimal control of an advection-reaction-diffusion equation and the optimal control of fluid flow past a cylinder. [ABSTRACT FROM AUTHOR]

In an iterative approach for solving linear systems with dense, ill-conditioned, symmetric positive definite (SPD) kernel matrices, both fast matrix-vector products and fast preconditioning operations are required. Fast (linear-scaling) matrix-vector products are available by expressing the kernel matrix in an H² representation or an equivalent fast multipole method representation.This paper is concerned with preconditioning such matrices using the hierarchically semi separable(HSS) matrix representation. Previously, an algorithm was presented to construct an HSS approx-imation to an SPD kernel matrix that is guaranteed to be SPD. However, this algorithm has qua-dratic cost and was only designed for recursive binary partitionings of the points defining the kernelmatrix. This paper presents a general algorithm for constructing an SPD HSS approximation. Importantly, the algorithm uses the scr H² representation of the SPD matrix to reduce its computational complexity from quadratic to quasi linear. Numerical experiments illustrate how this SPD HSS approximation performs as a pre conditioner for solving linear systems arising from a range of kernel functions. [ABSTRACT FROM AUTHOR]

In practical applications, incremental tensors are very common: only a portion of tensor data is available, and new data are arriving in the next time step or continuously over time. To handle this type of tensors time-saving algorithms are required for online computation. In this paper, we consider incremental CP ( CANDECOMP/PARAFAC ) decomposition, which requires one to update the CP decomposition after new tensor data, together with the exiting tensor, are ready for analysis. There exist several incremental CP decomposition algorithms, but almost all of these algorithms assume that the number of CP decomposition components remains fixed in the incremental process. The main contribution of this paper is the study of how to add components in the incremental CP decomposition. We derive the coordinate representation of the incremental CP decomposition with respect to a special basis and show related properties of tensor rank and the uniqueness of such incremental CP decomposition. Under the framework of this representation, the proposed method can be solved by using an alternating minimization algorithm. Numerical examples are presented to show the good performance of the proposed algorithms in terms of computational time and data fitting compared with existing methods. [ABSTRACT FROM AUTHOR]

This paper proposes some efficient and accurate adaptive two-grid (ATG) finite element algorithms for linear and nonlinear PDEs. The main idea of these algorithms is to utilize the solutions on the kth-level adaptive meshes to find the solutions on the (k + 1)th-level adaptive meshes which are constructed by performing adaptive element bisections on the k th-level adaptive meshes. These algorithms transform nonsymmetric positive definite (non-SPD) PDEs (resp., nonlinear PDEs) into symmetric positive definite (SPD) PDEs (resp., linear PDEs). The proposed algorithms are both accurate and efficient due to the following advantages: They do not need to solve the nonsymmetric or nonlinear systems; the degrees of freedom are very small, they are easily implemented, and the interpolation errors are very small. Next, this paper constructs residual-type a posteriori error estimators which are shown to be reliable and efficient. The key ingredient in proving the efficiency is to establish an upper bound of the oscillation terms, which may not be higher-order terms due to the low regularity of the numerical solution. Furthermore, the convergence of the algorithms is proved when bisection is used for the mesh refinements. Finally, numerical experiments are provided to verify the accuracy and efficiency of the ATG finite element algorithms compared to regular adaptive finite element algorithms and two-grid finite element algorithms [J. Xu, SIAM J. Numer. Anal., 33 (1996), pp. 1759-1777]. [ABSTRACT FROM AUTHOR]

In this paper, we resolve the one-pass space complexity of perfect Lp sampling for p ∈ (0, 2) in a stream. Given a stream of updates (insertions and deletions) to the coordinates of an underlying vector f ∈ ℝn, a perfect Lp sampler must output an index i with probability |fi|p/∥ f∥pp and is allowed to fail with some probability δ. So far, for p > 0 no algorithm has been shown to solve the problem exactly using poly(log n)-bits of space. In 2010, Monemizadeh and Woodruff introduced an approximate Lp sampler which, given an approximation parameter ν, outputs i with probability (1±ν)|fi| p/∥f∥pp, using space polynomial in ν-1 and log(n). The space complexity was later reduced by Jowhari, Sağlam, and Tardos to roughly O(ν-p log² n log δ-1) for p ∈ (0, 2), which matches the general p ≥ 0 lower bound of Ω (log² n log δ-1) in terms of n and δ, but is loose in terms of ν. Given these nearly tight bounds, it is perhaps surprising that no lower bound exists in terms of ν---not even a bound of Ω (ν-1) is known. In this paper, we explain this phenomenon by demonstrating the existence of an O(log² n log δ-1)-bit perfect Lp sampler for p ∈ (0, 2). This shows that ν need not factor into the space of an Lp sampler, which closes the complexity of the problem for this range of p. For p = 2, our bound is O(log³ n log δ-1)-bits, which matches the prior best known upper bound of O(ν-2 log³ n log δ-1), but has no dependence on ν. Note that there is still a log n gap between our upper bound and the lower bound for p = 2, the ution of which we leave as an open problem. For p < 2, our bound holds in the random oracle model, matching the lower bounds in that model. However, we show that our algorithm can be derandomized with only a O((log log n)²) blow-up in the space (and no blow-up for p = 2). Our derandomization technique is quite general, and can be used to derandomize a large class of linear sketches, including the more accurate count-sketch variant of Minton and Price [Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2014, pp. 669-686], resolving an open question in that paper. Finally, we show that a (1 ± ∈) relative error estimate of the frequency fi of the sampled index i can be obtained using an additional O(∈-p log n)-bits of space for p < 2, and O(∈-2 log² n) bits for p = 2, which was possible before only by running the prior algorithms with ν = ∈. [ABSTRACT FROM AUTHOR]

In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets of size k and EqualityTesting between vectors of length k. Sağglam and Tardos [Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678-687] and Brody et al. [Algorithmica, 76 (2016), pp. 796-845] showed that for these types of problems, one can achieve optimal communication volume of O(k) bits, with a randomized protocol that takes O(log* k) rounds. They also proved that this is one point along the optimal round-communication trade-off curve. Aside from rounds and communication volume, there is a third parameter of interest, namely the error probability perr, which we write 2-E. It is straightforward to show that protocols for SetIntersection or EqualityTesting need to send at least Ω (k + E) bits, regardless of the number of rounds. Is it possible to simultaneously achieve optimality in all three parameters, namely O(k + E) communication and O(log* k) rounds? In this paper we prove that there is no universally optimal algorithm, and we complement the existing round-communication trade-offs [M. Sağlam and G. Tardos, Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678-687; J. Brody et al., Algorithmica, 76 (2016), pp. 796-845] with a new trade-off between rounds, communication, and probability of error. In particular, any protocol for solving multiple EqualityTesting in r rounds with failure probability perr = 2-E has communication volume Ω (Ek1/r). We present several algorithms for multiple EqualityTesting (and its variants) that match or nearly match our lower bound and the lower bound of [M. Sağlam and G. Tardos, Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013, pp. 678-687; J. Brody et al., Algorithmica, 76 (2016), pp. 796-845]. Lower bounds on EqualityTesting extend to SetIntersection for every r, k, and perr (which is trivial); in the reverse direction, we prove that upper bounds on EqualityTesting for r, k, perr imply similar upper bounds on SetIntersection with parameters r + 1, k, and perr. Our original motivation for considering perr as an independent parameter came from the problem of enumerating triangles in distributed (CONGEST) networks having maximum degree Δ. We prove that this problem can be solved in O(Δ / log n+log log Δ) time with high probability 1 - 1/poly(n). This beats the trivial (deterministic) O(Δ)-time algorithm and is superior to the Õ(n1/3) algorithm of [Y. Chang, S. Pettie, and H. Zhang, Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 821-840; Y. Chang and T. Saranurak, Proceedings of the ACM Symposium on Principles of Distributed Computing, 2019, pp. 66-73] when Δ = Õ(n1/3). [ABSTRACT FROM AUTHOR]

In this paper, an easy to implement and efficient algorithm is proposed for large-scale sparse least squares problems. It reduces the original large-scale problem into a sequence of small-scale subproblems by utilizing the "sparsity" of the gradient. A well-designed FISTA algorithm is presented to solve the subproblems. With the desired termination criterion, the algorithm is proved to globally converge and converge locally at linear rate. Moreover, a complexity of O(mpln1ε) is given for the presented algorithm. Numerical comparisons between the presented algorithms and a number of state-of-the-art algorithms on solving LASSO problems with large-scale LIBSVM data sets and image deblurring problems demonstrate the robustness and high performance of the presented algorithms. As an example, the presented algorithm only needs 9 seconds to solve a LASSO problem with 19,264,097 samples and 29,890,095 features. [ABSTRACT FROM AUTHOR]

In this paper we describe a systematic procedure to analyze the convergence of degenerate preconditioned proximal point algorithms. We establish weak convergence results under mild assumptions that can be easily employed in the context of splitting methods for monotone inclusion and convex minimization problems. Moreover, we show that the degeneracy of the preconditioner allows for a reduction of the variables involved in the iteration updates. We show the strength of the proposed framework in the context of splitting algorithms, providing new simplified proofs of convergence and highlighting the link between existing schemes, such as Chambolle-Pock, forward Douglas-Rachford, and Peaceman-Rachford, that we study from a preconditioned proximal point perspective. The proposed framework allows us to devise new flexible schemes and provides new ways to generalize existing splitting schemes to the case of the sum of many terms. As an example, we present a new sequential generalization of forward Douglas-Rachford along with numerical experiments that demonstrates its interest in the context of nonsmooth convex optimization. [ABSTRACT FROM AUTHOR]

The golden ratio primal-dual algorithm (GRPDA) is a new variant of the classical Arrow-Hurwicz method for solving structured convex optimization problems, in which the objective function consists of the sum of two closed proper convex functions, one of which involves a composition with a linear transform. The same as the Arrow-Hurwicz method and the popular primal-dual algorithm (PDA) of Chambolle and Pock, GRPDA is full-splitting in the sense that it does not rely on solving any subproblems or linear system of equations iteratively. Compared with PDA, an important feature of GRPDA is that it permits larger primal and dual stepsizes. However, the stepsize condition of GRPDA requires that the spectral norm of the linear transform is known, which can be difficult to obtain in some applications. Furthermore, constant stepsizes are usually overconservative in practice. In this paper, we propose a linesearch strategy for GRPDA, which not only does not require the spectral norm of the linear transform but also allows adaptive and potentially much larger stepsizes. Within each linesearch step, only the dual variable needs to be updated, and it is thus quite cheap and does not require any extra matrix-vector multiplications for many special yet important applications such as a regularized least-squares problem. Global iterate convergence and 0(1/N) ergodic convergence rate results, measured by the function value gap and constraint violations of an equivalent optimization problem, are established, where N denotes the iteration counter. When one of the component functions is strongly convex, faster O(l/N²) ergodic convergence rate results, quantified by the same measures, are established by adaptively choosing some algorithmic parameters. Moreover, when the subdifferential operators of the component functions are strongly metric subregular, a condition that is much weaker than strong convexity, we show that the iterates converge R-linearly to the unique solution. Numerical experiments on matrix game and LASSO problems illustrate the effectiveness of the proposed linesearch strategy. [ABSTRACT FROM AUTHOR]

This paper is concerned with two improved variants of the Hutch++ algorithm for estimating the trace of a square matrix, implicitly given through matrix-vector products. Hutch++ combines randomized low-rank approximation in a first phase with stochastic trace estimation in a second phase. In turn, Hutch++ only requires O \bigl(\varepsilon 1 \bigr) matrix-vector products to approximate the trace within a relative error \varepsilon with high probability, provided that the matrix is symmetric positive semidefinite. This compares favorably with the O \bigl(\varepsilon 2 \bigr) matrix-vector products needed when using stochastic trace estimation alone. In Hutch++, the number of matrix-vector products is fixed a priori and distributed in a prescribed fashion among the two phases. In this work, we derive an adaptive variant of Hutch++, which outputs an estimate of the trace that is within some prescribed error tolerance with a controllable failure probability, while splitting the matrix-vector products in a near-optimal way among the two phases. For the special case of a symmetric positive semidefinite matrix, we present another variant of Hutch++, called Nystr\"om++, which utilizes the so-called Nystr\"om approximation and requires only one pass over the matrix, as compared to two passes with Hutch++. We extend the analysis of Hutch++ to Nystr\"om++. Numerical experiments demonstrate the effectiveness of our two new algorithms. [ABSTRACT FROM AUTHOR]

The "fast iterative shrinkage-thresholding algorithm,"" a.k.a. FISTA, is one of the most well known first-order optimization scheme in the literature, as it achieves the worst-case O(1/k2) optimal convergence rate for objective function value. However, despite such an optimal theoretical convergence rate, in practice the (local) oscillatory behavior of FISTA often damps its efficiency. Over the past years, various efforts have been made in the literature to improve the practical performance of FISTA, such as monotone FISTA, restarting FISTA, and backtracking strategies. In this paper, we propose a simple yet effective modification to the original FISTA scheme which has two advantages: It allows us to (1) prove the convergence of generated sequence and (2) design a so-called lazy-start strategy which can be up to an order faster than the original scheme. Moreover, we propose novel adaptive and greedy strategies which further improve the practical performance. The advantages of the proposed schemes are tested through problems arising from inverse problems, machine learning, and signal/image processing. [ABSTRACT FROM AUTHOR]

This paper develops algorithms for high-dimensional stochastic control problems based on deep learning and dynamic programming. Unlike classical approximate dynamic programming approaches, we first approximate the optimal policy by means of neural networks in the spirit of deep reinforcement learning, and then the value function by Monte Carlo regression. This is achieved in the dynamic programming recursion by performance or hybrid iteration and regress-now methods from numerical probabilities. We provide a theoretical justification of these algorithms. Consistency and rate of convergence for the control and value function estimates are analyzed and expressed in terms of the universal approximation error of the neural networks, and of the statistical error when estimating network function, leaving aside the optimization error. Numerical results on various applications are presented in a companion paper [Deep neural networks algorithms for stochastic control problems on finite horizon: Numerical applications, Methodol. Comput. Appl. Probab., to appear] and illustrate the performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

This paper is concerned with the inverse acoustic scattering problem with phaseless total-field data at a fixed frequency. An approximate factorization method is developed to numerically reconstruct both the location and shape of the unknown scatterer from the phaseless total-field data generated by incident plane waves at a fixed frequency and measured on the circle \partial BR with a sufficiently large radius R. The theoretical analysis of our method is based on the asymptotic property in the operator norm from H1/2(S1) to H 1/2(S1) of the phaseless total-field operator defined in terms of the phaseless total-field data measured on \partial BR with large enough R, where Hs(S1) is a Sobolev space on the unit circle S1 for real number s, together with the factorization of a modified far-field operator. The asymptotic property of the phaseless total-field operator is also established in this paper with the theory of oscillatory integrals. The unknown scatterer can be either an impenetrable obstacle of sound-soft, sound-hard, or impedance type, or an inhomogeneous medium with a compact support, and the proposed inversion algorithm does not need to know the boundary condition of the unknown obstacle in advance. Numerical examples are also carried out to demonstrate the effectiveness of our inversion method. To the best of our knowledge, this is the first attempt to develop a factorization type method for inverse scattering problems with phaseless data. [ABSTRACT FROM AUTHOR]

In this paper, we study smooth stochastic multilevel composition optimization problems, where the objective function is a nested composition of T functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze their convergence to an e-stationary point of the problem. We show that the first algorithm, which is a generalization of [S. Ghadimi, A. Ruszczynski, and M. Wang, SIAM J. Optim., 30 (2020), pp. 960-979] to the T level case, can achieve a sample complexity of OT(1/ε6) by using minibatches of samples in each iteration, where OT hides constants that depend on T. By modifying this algorithm using linearized stochastic estimates of the function values, we improve the sample complexity to OT(1/ε4). This modification not only removes the requirement of having a minibatch of samples in each iteration, but also makes the algorithm parameter-free and easy to implement. To the best of our knowledge, this is the first time that such an online algorithm designed for the (un)constrained multilevel setting obtains the same sample complexity of the smooth single-level setting, under standard assumptions (unbiasedness and boundedness of the second moments) on the stochastic first-order oracle. [ABSTRACT FROM AUTHOR]

In this paper we consider wave propagation problems in two-dimensional unbounded domains, including dissipative effects, reformulated in terms of space-time boundary integral equations. For their solution, we employ a convolution quadrature (CQ) for the temporal and a Galerkin boundary element method (BEM) for the spatial discretization. It is known that one of the main advantages of the CQ-BEMs is the use of the FFT algorithm to retrieve the discrete time integral operators with an optimal linear complexity in time, up to a logarithmic term. It is also known that a key ingredient for the success of such methods is the efficient and accurate evaluation of all the integrals that define the matrix entries associated to the full space-time discretization. This topic has been successfully addressed when standard Lagrangian basis functions are considered for the space discretization. However, it results that, for such a choice of the basis, the BEM matrices are in general fully populated, a drawback that prevents the application of CQ-BEMs to large-scale problems. In this paper, as a possible remedy to reduce the global complexity of the method, we consider approximant functions of wavelet type. In particular, we propose a numerical procedure that, by taking advantage of the fast wavelet transform, allows us on the one hand to compute the matrix entries associated to the choice of wavelet basis functions by maintaining the accuracy of those associated to the Lagrangian basis ones and, on the other hand, to generate sparse matrices without the need of storing a priori the fully populated ones. Such an approach allows in principle the use of wavelet basis of any type and order, combined with CQ based on any stable ordinary differential equations solver. Several numerical results, showing the accuracy of the solution and the gain in terms of computer memory saving, are presented and discussed. [ABSTRACT FROM AUTHOR]

We introduce a new feasible corrector-predictor (CP) interior-point algorithm (IPA), which is suitable for solving linear complementarity problem (LCP) with P* (K)-matrices. We use the method of algebraically equivalent transformation (AET) of the nonlinear equation of the system which defines the central path. The AET is based on the function φ(ί) = t -- t and plays a crucial role in the calculation of the new search direction. We prove that the algorithm has O iteration complexity, where κ is an upper bound of the handicap of the input matrix. To the best of our knowledge, this is the first CP IPA for P*(κ)-LCPs which is based on this search direction. We implement the proposed CP IPA in the C++ programming language with specific parameters and demonstrate its performance on three families of LCPs. The first family consists of LCPs with P* (K)-matrices. The second family of LCPs has the P-matrix defined by Csizmadia. Eisenberg-Nagy and de Klerk [Math. Program., 129 (2011), pp. 383--402] showed that the handicap of this matrix should be at least 22n--8 -- 1/4. Namely, from the known complexity results for P*(κ)-LCPs it might follow that the computational performance of IPAs on LCPs with the matrix defined by Csizmadia could be very poor. Our preliminary computational study shows that an implemented variant of the theoretical version of the CP IPA (Algorithm 4.1) presented in this paper, finds a e-approximate solution for LCPs with the Csizmadia matrix in a very small number of iterations. The third family of problems consists of the LCPs related to the copositivity test of 88 matrices from [C. Bras, G. Eichfelder, and J. Judice, Comput. Optim. Appl., 63 (2016), pp. 461--493]. For each of these matrices we create a special LCP and try to solve it using our IPA. If the LCP does not have a solution, then the related matrix is strictly copositive, otherwise it is on the boundary or outside the copositive cone. For these LCPs we do not know whether the underlying matrix is P*(k) or not, but we could reveal the real copositivity status of the input matrices in 83 out of 88 cases (accuracy ≤ 94%). The numerical test shows that our CP IPA performs well on the sets of test problems used in the paper. [ABSTRACT FROM AUTHOR]

In this paper, we develop the ball-approximated characteristics (B-char) method, which is an algorithm for efficiently implementing characteristic-based schemes in two and three dimensions. Core to the implementation of numerical schemes is the evaluation of integrals, which in the context of characteristic-based schemes with piecewise constant approximations boils down to computing the intersections between two regions. In the literature, these regions are approximated by polytopes (polygons in two dimensions and polyhedra in three dimensions) and, due to this, the implementation in three dimensions is nontrivial. The main novelty in this paper is the approximation of the regions by balls, whose intersections are much cheaper to compute than those of polytopes. Of course, balls cannot fully tessellate a region, and hence some mass may be lost. We perform some adjustments, and also solve an optimization problem, in order to yield a scheme that is both locally and globally mass conserving. This algorithm can achieve results that are similar to those obtained from an implementation which uses polytopal intersections, with a much cheaper computational cost. [ABSTRACT FROM AUTHOR]

This paper presents a multilevel convergence framework for multigrid-reduction-intime (MGRIT) as a generalization of previous two-grid estimates. The framework provides a priori upper bounds on the convergence of MGRIT V- and F-cycles, with different relaxation schemes, by deriving the respective residual and error propagation operators. The residual and error operators are functions of the time-stepping operator, analyzed directly and bounded in the norm, both numerically and analytically. We present various upper bounds of different computational cost and varying sharpness. These upper bounds are complemented by proposing analytic formulae for the approximate convergence factor of V-cycle algorithms that take the number of fine grid time points, the temporal coarsening factors, and the eigenvalues of the time-stepping operator as parameters. The paper concludes with supporting numerical investigations of parabolic (anisotropic diffusion) and hyperbolic (wave equation) model problems. We assess the sharpness of the bounds and the quality of the approximate convergence factors. Observations from these numerical investigations demonstrate the value of the proposed multilevel convergence framework for estimating MGRIT convergence a priori and for the design of a convergent algorithm. We further highlight that observations in the literature are captured by the theory, including that two-level Parareal and multilevel MGRIT with F-relaxation do not yield scalable algorithms and the benefit of a stronger relaxation scheme. An important observation is that with increasing numbers of levels MGRIT convergence deteriorates for the hyperbolic model problem, while constant convergence factors can be achieved for the diffusion equation. The theory also indicates that L-stable Runge--Kutta schemes are more amendable to multilevel parallel-in-time integration with MGRIT than A-stable Runge--Kutta schemes. [ABSTRACT FROM AUTHOR]

Two asymptotically exact a posteriori error estimates are proposed for eigenvalues by the nonconforming Crouzeix--Raviart and enriched Crouzeix--Raviart elements. The main challenge in the design of such error estimators comes from the nonconformity of the finite element spaces used. Such nonconformity causes two difficulties: the first is the construction of high accuracy gradient recovery algorithms, and the second is a computable high accuracy approximation of a consistency error term. The first difficulty was solved for both nonconforming elements in a previous paper. Two methods are proposed to solve the second difficulty in the present paper. In particular, this solution allows the use of high accuracy gradient recovery techniques. Further, a postprocessing algorithm is designed by utilizing asymptotically exact a posteriori error estimators to construct the weights of a combination of two approximate eigenvalues. This algorithm requires solving only one eigenvalue problem and admits high accuracy eigenvalue approximations both theoretically and numerically. [ABSTRACT FROM AUTHOR]

We systematically study a numerical procedure that reveals the asymptotically selfsimilar dynamics of solutions of partial differential equations (PDEs). This procedure, based on the renormalization group (RG) theory for PDEs, appeared initially in a conference proceedings [G. A. Braga, F. Furtado, and V. Isaia, in Proceedings of the Fifth International Conference on Dynamical Systems and Differential Equations, Pomona, CA, 2004, pp. 1--13]. A numerical version of the RG method, dubbed nRG, rescales the temporal and spatial variables in each iteration and drives the solutions to a fixed point exponentially fast, which corresponds to the self-similar dynamics of the equations. In this paper, we carefully examine and validate this class of algorithms by comparing the numerical solutions with either exact or asymptotic solutions of model equations found in the literature. The other contribution of the current paper is that we present several examples to demonstrate that this class of nRG algorithms can be applied to a wide range of PDEs to shed light on long time self-similar dynamics of certain physical systems modeled by PDEs. [ABSTRACT FROM AUTHOR]

Recent papers indicate that some algorithms for constrained optimization may exhibit worst-case complexity bounds that are very similar to those of unconstrained optimization algorithms. A natural question is whether well-established practical algorithms, perhaps with small variations, may enjoy analogous complexity results. In the present paper we show that the answer is positive with respect to inexact restoration algorithms in which first-order approximations are employed for defining the subproblems. [ABSTRACT FROM AUTHOR]

In this paper, we extend the original criss-cross algorithms for computing the\varepsilon-pseudospectral abscissa and radius to general spectral value sets. By proposing new root-findingbased strategies for the horizontal/radial search subphases, we significantly reduce the number of expensive Hamiltonian eigenvalue decompositions incurred, which typically translates to meaningful speedups in overall computation times. Furthermore, and partly necessitated by our root-finding approach, we develop a new way of handling the singular pencils or problematic interior searches that can arise when computing the\varepsilon-spectral value set radius. Compared to would-be direct extensions of the original algorithms, that is, without our additional modifications, our improved criss-cross algorithms are not only noticeably faster but also more robust and numerically accurate, for both spectral value set and pseudospectral problems. [ABSTRACT FROM AUTHOR]

The paper considers a Jacobi method for solving the generalized eigenvalue problem Ax = λBx, where A and B are complex Hermitian matrices and B is positive definite. The method is a proper generalization of the standard Jacobi method for the Hermitian matrix A to the matrix pair (A,B). The paper derives the method and proves its global convergence under the large class of generalized serial pivot strategies. If both matrices are positive definite, it can be implemented as a one-sided method. It then solves the initial problem as the generalized singular value problem. Its main application is to serve as a kernel algorithm in a block Jacobi method for the same problem with large matrices A and B. The block Jacobi methods are methods of choice on contemporary CPU and GPU computing architectures. The proposed algorithm is very efficient on pairs of almost diagonal matrices, and diagonalization of such matrices is the main task of the kernel algorithm. The numerical tests indicate the high relative accuracy of the method on certain pairs of positive definite matrices. [ABSTRACT FROM AUTHOR]

A (β; ε)-hopset for a weighted undirected n-vertex graph G = (V,E) is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most β edges, whose length is within 1 + ε of the shortest path. In her seminal paper, Cohen [J. ACM, 47 (2000), pp. 132-166] introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen [J. ACM, 47 (2000), pp. 132-166] devised efficient algorithms for constructing hopsets with polylogarithmic in n number of hops. Her constructions remain the state of the art since the publication of her paper in the proceedings of STOC'94, i.e., for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a constant number of hops. We also find efficient algorithms for hopsets in various computational settings, improving the best-known constructions. Generally, our hopsets strictly outperform the hopsets of [J. ACM, 47 (2000), pp. 132-166] in terms of both their parameters and the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from s sources. Our results improve the running time for this problem in the parallel, distributed, and streaming models for a vast range of s. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of single-ratio fractional minimization problems, in which the numerator of the objective is the sum of a nonsmooth nonconvex function and a smooth nonconvex function while the denominator is a nonsmooth convex function. In this work, we first derive its first-order necessary optimality condition, by using the first-order operators of the three functions involved. Then we develop first-order algorithms, namely, the proximity-gradientsubgradient algorithm (PGSA), PGSA with monotone line search (PGSA ML), and PGSA with nonmonotone line search (PGSA NL). It is shown that any accumulation point of the sequence generated by them is a critical point of the problem under mild assumptions. Moreover, we establish global convergence of the sequence generated by PGSA or PGSA ML and analyze its convergence rate, by further assuming the local Lipschitz continuity of the nonsmooth function in the numerator, the smoothness of the denominator, and the Kurdyka--Łojasiewicz (KL) property of the objective. The proposed algorithms are applied to the sparse generalized eigenvalue problem associated with a pair of symmetric positive semidefinite matrices, and the corresponding convergence results are obtained according to their general convergence theorems. We perform some preliminary numerical experiments to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Nonnegative matrix factorization (NMF) is a useful method to extract features from multivariate data, but an important and sometimes neglected concern is that NMF can result in nonunique solutions. Often, there exist a set of feasible solutions (SFS), which makes it more difficult to interpret the factorization. This problem is especially ignored in cancer genomics, where NMF is used to infer information about the mutational processes present in the evolution of cancer. In this paper the extent of nonuniqueness is investigated for two mutational counts data, and a new sampling algorithm that can find the SFS is introduced. Our sampling algorithm is easy to implement and applies to an arbitrary rank of NMF. This is in contrast to state of the art, where the NMF rank must be smaller than or equal to four. For lower ranks we show that our algorithm performs similar to the polygon inflation algorithm that is developed in relation to chemometrics. Furthermore, we show how the size of the SFS can have a high influence on the appearing variability of a solution. Our sampling algorithm is implemented in the R package SFS (https://github.com/ragnhildlaursen/SFS). [ABSTRACT FROM AUTHOR]

Policy optimization (PO) is a key ingredient for modern reinforcement learning. For control design, certain constraints are usually enforced on the policies to optimize, accounting for stability, robustness, or safety concerns on the system. Hence, PO is by nature a constrained (non-convex) optimization in most cases, whose global convergence is challenging to analyze in general. More importantly, some constraints that are safety-critical, e.g., the closed-loop stability, or the H-∞ norm constraint that guarantees the system robustness, can be difficult to enforce on the controller being learned as the PO methods proceed. In this paper, we study the convergence theory of PO for H2 linear control with H∞ robustness guarantee. This general framework includes risk-sensitive linear control as a special case. One significant new feature of this problem, in contrast to the standard H2 linear control, namely, linear quadratic regulator problems, is the lack of coercivity of the cost function. This makes it challenging to guarantee the feasibility, namely, the H∞ robustness, of the iterates. Interestingly, we propose two PO algorithms that enjoy the implicit regularization property, i.e., the iterates preserve the H∞ robustness automatically, as if they are regularized. Furthermore, despite the nonconvexity of the problem, we show that these algorithms converge to a certain globally optimal policy with globally sublinear rates, without getting stuck at any other possibly suboptimal stationary points, and with locally (super)linear rates under additional conditions. To the best of our knowledge, our work offers the first results on the implicit regularization property and global convergence of PO methods for robust/risk-sensitive control. [ABSTRACT FROM AUTHOR]

The need to solve l¹ regularized linear problems can be motivated by various compressive sensing and sparsity related techniques for data analysis and signal or image processing. These problems lead to nonsmooth convex optimization in high dimensions. Theoretical works predict a sharp phase transition for the exact recovery of compressive sensing problems. Our numerical experiments show that state-of-the-art algorithms are not effective enough to observe this phase transition accurately. This paper proposes a simple formalism that enables us to produce an algorithm that computes an l¹ minimizer under the constraints Au = b up to the machine precision. In addition, a numerical comparison with standard algorithms available in the literature is exhibited. The comparison shows that our algorithm compares advantageously with other state-of-the-art methods, both in terms of accuracy and efficiency. With our algorithm, the aforementioned phase transition is observed at high precision. [ABSTRACT FROM AUTHOR]

In this paper, we propose a parallel-in-time algorithm for approximately solving parabolic equations. In particular, we apply the k-step backward differentiation formula and then develop an iterative solver by using the waveform relaxation technique. Each resulting iteration represents a periodic-like system, which could be further solved in parallel by using the diagonalization technique. The convergence of the waveform relaxation iteration is theoretically examined by using the generating function method. The argument could be further applied to the time-fractional subdiffusion equation, whose discretization shares common properties of the standard BDF methods due to the nonlocality of the fractional differential operator. Illustrative numerical results are presented to complement the theoretical analysis. [ABSTRACT FROM AUTHOR]

The article highlights two papers published within the issue titled "Divide-and-Conquer: A Proportional, Minimal-Envy Cake-Cutting Algorithm," by Steven Brams, Michael Jones and Christian Klamler, and "Impossibility of Fast Stable Approximation of Analytic Functions from Equispaced Samples," by Rodrigo Platte, Lloyd Trefethen and Arno Kuijlaars. The first paper discussed the mathematical problem of proportional division. The second one talked about potential theory, matrix iterations in the form of Krylov space methods and quadrature formulae.

In this paper we propose an approximation method for high-dimensional 1-periodic functions based on the multivariate ANOVA decomposition. We provide an analysis on the classical ANOVA decomposition on the torus and prove some important properties such as the inheritance of smoothness for Sobolev type spaces and the weighted Wiener algebra. We exploit special kinds of sparsity in the ANOVA decomposition with the aim to approximate a function in a scattered data or black-box approximation scenario. This method allows us to simultaneously achieve an importance ranking on dimensions and dimension interactions which is referred to as attribute ranking in some applications. In scattered data approximation we rely on a special algorithm based on the non-equispaced fast Fourier transform (or NFFT) for fast multiplication with arising Fourier matrices. For black-box approximation we choose the well-known rank-1 lattices as sampling schemes and show properties of the appearing special lattices [ABSTRACT FROM AUTHOR]

This paper presents new results on nonseparating cocircuits in binary matroids. The first result states that for any 3-connected binary matroid M and for any basis B of M, there exists at least two nonseparating B-fundamental cocircuits in M. The second result provides a weakened version of this result for nonseparable binary matroids that are also simple and cosimple. The final states that if M is a nonseparable binary matroid, D is a nonseparating cocircuit of M, and e is an element of D, then M is graphic if and only if M/e is graphic and has a realization H in which D \{ e\} is a subset of the star of some node of H. All of these results are shown to lead to efficient algorithms. [ABSTRACT FROM AUTHOR]

Least squares form one of the most prominent classes of optimization problems with numerous applications in scientific computing and data fitting. When such formulations aim at modeling complex systems, the optimization process must account for nonlinear dynamics by incorporating constraints. In addition, these systems often incorporate a large number of variables, which increases the difficulty of the problem and motivates the need for efficient algorithms amenable to large-scale implementations. In this paper, we propose and analyze a Levenberg--Marquardt algorithm for nonlinear least squares subject to nonlinear equality constraints. Our algorithm is based on inexact solves of linear least-squares problems that only require Jacobian-vector products. Global convergence is guaranteed by the combination of a composite step approach and a nonmonotone step acceptance rule. We illustrate the performance of our method on several test cases from data assimilation and inverse problems; our algorithm is able to reach the vicinity of a solution from an arbitrary starting point and can outperform the most natural alternatives for these classes of problems. [ABSTRACT FROM AUTHOR]

The paper considers supervised learning problems of labeled data with grouped input features. The groups are nonoverlapped such that the model coefficients corresponding to the input features form disjoint groups. The coefficients have group sparsity structure in the sense that coefficients corresponding to each group shall be simultaneously either zero or nonzero. To make effective use of such group sparsity structure given a priori, we introduce a novel log-composite regularizer, which can be minimized by an iterative algorithm. In particular, our algorithm iteratively solves for a traditional group least absolute shrinkage and selection operator (LASSO) problem that involves summing up the l2 norm of each group until convergent. By updating group weights, our approach enforces a group of smaller coefficients from the previous iterate to be more likely to set to zero compared to the group LASSO. Theoretical results include a minimizing property of the proposed model as well as the convergence of the iterative algorithm to a stationary solution under mild conditions. We conduct extensive experiments on synthetic and real datasets, indicating that our method yields a performance that is superior to that of the state-of-the-art methods in linear regression and binary classification. [ABSTRACT FROM AUTHOR]

When using Laguerre and Hermite spectral methods to numerically solve PDEs in unbounded domains, the number of collocation points assigned inside the region of interest is often insufficient, particularly when the region is expanded or translated in order to safely capture the unknown solution. Simply increasing the number of collocation points cannot ensure a fast convergence to spectral accuracy. In this paper, we propose a scaling technique and a moving technique to adaptively cluster enough collocation points in a region of interest in order to achieve fast spectral convergence. Our scaling algorithm employs an indicator in the frequency domain that both is used to determine when scaling is needed and informs the tuning of a scaling factor to redistribute collocation points in order to adapt to the diffusive behavior of the solution. Our moving technique adopts an exterior-error indicator and moves the collocation points to capture the translation. Both frequency and exterior-error indicators are defined using only the numerical solutions. We apply our methods to a number of different models, including diffusive and moving Fermi-Dirac distributions and nonlinear Dirac solitary waves, and demonstrate recovery of spectral convergence for time-dependent simulations. A performance comparison in solving a linear parabolic problem shows that our frequency scaling algorithm outperforms the existing scaling approaches. We also show our frequency scaling technique is able to track the blowup of average cell sizes in a model for cell proliferation. In addition to the Laguerre and Hermite basis functions with exponential decay at infinity, we also successfully apply the frequency-dependent scaling technique into rational basis functions with algebraic decay at infinity. [ABSTRACT FROM AUTHOR]

This paper develops an adaptive LQ based disturbance rejection solution for continuous-time possibly nonminimum-phase systems with uncertainties from both dynamics and unmatched input disturbances, using a reduced Hamiltonian function for performance improvement. Such a reduced Hamiltonian LQ control framework is constructed by using a control-separation design and a reduced cost function, with which a two-component controller structure is employed for the desired control objectives: one component dealing with disturbance rejection and one component dealing with system stabilization and output regulation. Such a new control design is first developed for nominal (uncertainty-free) control-separation LQ solutions using reduced Hamiltonian under different relative degree conditions and for finite-time and infinite-time cases and is demonstrated to have the capability to improve system performance as compared with traditional LQ solutions. Based on the developed new controller structure, the adaptive disturbance rejection problem is solved by developing a stable adaptive parameter estimation algorithm for the two-component control law, to ensure desired system stabilization and output regulation in the presence of system and disturbance uncertainties. Simulation results are shown to verify the effectiveness of our proposed LQ based disturbance rejection control schemes. [ABSTRACT FROM AUTHOR]

This paper proposes a new and efficient numerical algorithm for recovering the damping coefficient from the spectrum of a damped wave operator. The algorithm is based on inverting a sequence of trace formulas, which are deduced by a recursive formula, bridging geometrical and spectrum information explicitly in terms of Fredholm integral equations. Numerical examples are presented to illustrate the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Dynamical low-rank algorithms are a class of numerical methods that compute lowrank approximations of dynamical systems. This is accomplished by projecting the dynamics onto a low-dimensional manifold and writing the solution directly in terms of the low-rank factors. The approach has been successfully applied to many types of differential equations. Recently, efficient dynamical low-rank algorithms have been proposed in [L. Einkemmer, A Low-Rank Algorithm for Weakly Compressible Flow, arXiv:1804.04561, 2018; L. Einkemmer and C. Lubich, SIAM J. Sci. Comput., 40 (2018), pp. B1330-B1360] to treat kinetic equations, including the Vlasov-Poisson and the Boltzmann equation. There it was demonstrated that the methods are able to capture the lowrank structure of the solution and significantly reduce numerical cost, while often maintaining high accuracy. However, no numerical analysis is currently available. In this paper, we perform an error analysis for a dynamical low-rank algorithm applied to the multiscale linear Boltzmann equation (a classical model in kinetic theory) to showcase the validity of the application of dynamical lowrank algorithms to kinetic theory. The equation, in its parabolic regime, is known to be rank 1 theoretically, and we will prove that the scheme can dynamically and automatically capture this low-rank structure. This work thus serves as the first mathematical error analysis for a dynamical low-rank approximation applied to a kinetic problem. [ABSTRACT FROM AUTHOR]

Sparsity regularization has been widely adopted in many fields, such as signal and image processing and machine learning. In this paper, we mainly consider nonconvex minimization problems involving three terms, for applications such as sparse signal recovery and low rank matrix recovery. We employ a three-operator splitting proposed by Davis and Yin [Set-Valued Var. Anal., 25 (2017), pp. 829-858] (namely, DYS) to solve the resulting possibly nonconvex problems and develop the convergence theory for this three-operator splitting algorithm in the nonconvex case. We show that when the step size is chosen less than a computable threshold, the whole sequence converges to a stationary point. By defining a new decreasing energy function associated with the DYS method, we establish the global convergence of the whole sequence and a local convergence rate under an additional assumption that F, G, and H are semialgebraic. We also provide sufficient conditions for the boundedness of the generated sequence. Finally, some numerical experiments are conducted to compare the DYS algorithm with some classical efficient algorithms for sparse signal recovery and low rank matrix completion. The numerical results indicate that DYS outperforms the existing methods for these applications. [ABSTRACT FROM AUTHOR]

When solving partial differential equations (PDEs) with random fields as coefficients, the efficient sampling of random field realizations can be challenging. In this paper we focus on the fast sampling of Gaussian fields using quasi-random points in a finite element and multilevel quasi Monte Carlo (MLQMC) setting. Our method uses the stochastic PDE (SPDE) approach of Lindgren et al. combined with a new fast algorithm for white noise sampling which is tailored to (ML)QMC. We express white noise as a wavelet series expansion that we divide into two parts. The first part is sampled using quasi-random points and contains a finite number of terms in order of decaying importance to ensure good quasi Monte Carlo (QMC) convergence. The second part is a correction term which is sampled using standard pseudo-random numbers. We show how the sampling of both terms can be performed in linear time and memory complexity in the number of mesh cells via a supermesh construction, yielding an overall linear cost. Furthermore, our technique can be used to enforce the MLQMC coupling even in the case of nonnested mesh hierarchies. We demonstrate the efficacy of our method with numerical experiments. [ABSTRACT FROM AUTHOR]

In many multiphysics applications, an ultimate quantity of interest can be written as a linear functional of the solution to the discretized governing nonlinear partial differential equations and finding a sufficiently accurate pointwise solution may be regarded as a step toward that end. In this paper, we derive a posteriori approximate error bounds for linear functionals corresponding to quantities of interest using two kinds of nonlinear preconditioning techniques. Nonlinear preconditioning, such as the inexact Newton with backtracking and nonlinear elimination algorithm and the multiplicative Schwarz preconditioned inexact Newton algorithm, may be effective in improving global convergence for Newton's method. It may prevent stagnation of the nonlinear residual norm and reduce the number of solutions of large ill-conditioned linear systems involving a global Jacobian required at each nonlinear iteration. We illustrate the effectiveness of the new bounds using canonical nonlinear PDE models: a flame sheet model and a nonlinear coupled lid-driven cavity problem. [ABSTRACT FROM AUTHOR]

In this paper we propose an efficient method to compress a high dimensional function into a tensor ring format, based on alternating least squares (ALS). Since the function has size exponential in d, where d is the number of dimensions, we propose an efficient sampling scheme to obtain O(d) important samples in order to learn the tensor ring. Furthermore, we devise an initialization method for ALS that allows fast convergence in practice. Numerical examples show that to approximate a function with similar accuracy, the tensor ring format provided by the proposed method has fewer parameters than the tensor-train format and also better respects the structure of the original function. [ABSTRACT FROM AUTHOR]

This paper presents a framework based on matrices of monoids for the study of coupled cell networks. We formally prove within the proposed framework, that the set of results about invariant synchrony patterns for unweighted networks also holds for the weighted case. Moreover, the approach described allows us to reason about any multiedge and multiedge-type network as if it was single edge and single-edge-type. Several examples illustrate the concepts described. Additionally, an improvement of the coarsest invariant refinement algorithm to find balanced partitions is presented that exhibits a worst-case complexity of O (|C|³), where rC denotes the set of cells. [ABSTRACT FROM AUTHOR]

This paper studies bilevel polynomial optimization. We propose a method to solve it globally by using polynomial optimization relaxations. Each relaxation is obtained from the Karush-Kuhn-Tucker (KKT) conditions for the lower level optimization and the exchange technique for semi-infinite programming. For KKT conditions, Lagrange multipliers are represented as polynomial or rational functions. The Moment-sum-of-squares relaxations are used to solve the polynomial optimization relaxations. Under some general assumptions, we prove the convergence of the algorithm for solving bilevel polynomial optimization problems. Numerical experiments are presented to show the efficiency of the method. [ABSTRACT FROM AUTHOR]

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$, and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbb{Q}$-rank-width, rank-width, and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic \sf NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [B. Bui-Xuan, J. A. Telle, and M. Vatshelle, Theoret. Comput. Sci., (2013), pp. 66--76] and the rank-based approach introduced in [H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof, Inform. and Comput., 243 (2015), pp. 86--111]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for ${\sf W}[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$, and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbb{Q}$-rank-width, and the rank-width of the input graph. [ABSTRACT FROM AUTHOR]

Diffusion maps is a manifold learning algorithm widely used for dimensionality reduction. Using a sample from a distribution, it approximates the eigenvalues and eigenfunctions of associated Laplace-Beltrami operators. Theoretical bounds on the approximation error are, however, generally much weaker than the rates that are seen in practice. This paper uses new approaches to improve the error bounds in the model case where the distribution is supported on a hypertorus. For the data sampling (variance) component of the error we make spatially localized compact embedding estimates on certain Hardy spaces; we study the deterministic (bias) component as a perturbation of the Laplace-Beltrami operator's associated PDE and apply relevant spectral stability results. Using these approaches, we match long-standing pointwise error bounds for both the spectral data and the norm convergence of the operator discretization. We also introduce an alternative normalization for diffusion maps based on Sinkhorn weights. This normalization approximates a Langevin diffusion on the sample and yields a symmetric operator approximation. We prove that it has better convergence compared with the standard normalization on flat domains, and we present a highly efficient rigorous algorithm to compute the Sinkhorn weights. [ABSTRACT FROM AUTHOR]

In ptychography experiments, redundant scanning is usually required to guarantee the stable recovery, such that a huge number of frames are generated, and thus it poses a great demand on parallel computing to solve this large-scale inverse problem. In this paper, we propose the overlapping domain decomposition methods to solve the nonconvex optimization problem in ptychographic imaging. They decouple the problem defined on the whole domain into subproblems only defined on the subdomains with synchronizing information in the overlapping regions of these subdomains, thus leading to highly parallel algorithms with good load balance. More specifically, for the nonblind recovery (with known probe in advance), by enforcing the continuity of the overlapping regions for the image (sample), the nonlinear optimization model is established based on a novel smooth-truncated amplitude-Gaussian metric (ST-AGM). Such a metric allows for fast calculation of the proximal mapping with closed form, and meanwhile provides the possibility for the convergence guarantee of the first-order nonconvex optimization algorithm due to its Lipschitz smoothness. Then the alternating direction method of multipliers is utilized to generate an efficient overlapping domain decomposition based ptychography algorithm (OD2P) for the two-subdomain domain decomposition (DD), where all subproblems can be computed with closed-form solutions. Due to the Lipschitz continuity for the gradient of the objective function with ST-AGM, the convergence of the proposed OD2P is derived under mild conditions. Moreover, it is extended to more general cases including multiple-subdomain DD and blind recovery. Numerical experiments are further conducted to show the performance of proposed algorithms, demonstrating good convergence speed and robustness to the noise. Especially, we report the virtual wall-clock time of proposed algorithm up to 10 processors, which shows potential for upcoming massively parallel computations. [ABSTRACT FROM AUTHOR]

In this paper, we consider a nonlinear and nonlocal parabolic model for multispecies ionic fluids and introduce a semi-implicit finite volume scheme, which is second-order accurate in space, is first-order in time, and satisfies the positivity preserving and mass conservation properties. The scheme also satisfies an energy dissipation relation at the semidiscrete level. In addition, our scheme involves a fast algorithm on the convolution terms with singular but integrable kernels on the uniform grid, which otherwise impedes the accuracy and efficiency of the whole scheme. Error estimates on the fast convolution algorithm are shown next. Numerous numerical tests are provided to demonstrate the properties, such as unconditional stability, the order of convergence, energy dissipation, and the complexity of the fast convolution algorithm. Furthermore, extensive numerical experiments are carried out to explore the modeling effects in specific examples, such as the steric repulsion, concentration of ions at the boundary, and blowup phenomenon of Keller--Segel equations. [ABSTRACT FROM AUTHOR]

Large-scale optimization problems arising from the discretization of problems involving PDEs sometimes admit solutions that can be well approximated by low-rank matrices. In this paper, we will exploit this low-rank approximation property by solving the optimization problem directly over the set of low-rank matrices. In particular, we introduce a new multilevel algorithm, where the optimization variable is constrained to the Riemannian manifold of fixed-rank matrices. In contrast to most other multilevel algorithms, where the rank is chosen adaptively on each level in order to control the perturbation due to the low-rank truncation, we can keep the ranks (and thus the computational complexity) fixed throughout the iterations. Furthermore, classical implementations of line searches based on Wolfe conditions enable computing a solution where the numerical accuracy is limited to about the square root of the machine epsilon. Here, we propose an extension to Riemannian manifolds of the line search of Hager and Zhang, which uses approximate Wolfe conditions that enable computing a solution on the order of the machine epsilon. Numerical experiments demonstrate the computational efficiency of the proposed framework. [ABSTRACT FROM AUTHOR]