Search

A lattice of integers is the collection of all linear combinations of a set of vectors for which all entries of the vectors are integers and all coefficients in the linear combinations are also integers. Lattice reduction refers to the problem of finding a set of vectors in a given lattice such that the collection of all integer linear combinations of this subset is still the entire original lattice and so that the Euclidean norms of the subset are reduced. The present paper proposes simple, efficient iterations for lattice reduction which are guaranteed to reduce the Euclidean norms of the basis vectors (the vectors in the subset) monotonically during every iteration. Each iteration selects the basis vector for which projecting off (with integer coefficients) the components of the other basis vectors along the selected vector minimizes the Euclidean norms of the reduced basis vectors. Each iteration projects off the components along the selected basis vector and efficiently updates all information required for the next iteration to select its best basis vector and perform the associated projections. [ABSTRACT FROM AUTHOR]

The implicit trace estimation problem asks for an approximation of the trace of a square matrix, accessed via matrix-vector products (matvecs). This paper designs new randomized algorithms, XTrace and XNysTrace, for the trace estimation problem by exploiting both variance reduction and the exchangeability principle. For a fixed budget of matvecs, numerical experiments show that the new methods can achieve errors that are orders of magnitude smaller than existing algorithms, such as the Girard--Hutchinson estimator or the Hutch++ estimator. A theoretical analysis confirms the benefits by offering a precise description of the performance of these algorithms as a function of the spectrum of the input matrix. The paper also develops an exchangeable estimator, XDiag, for approximating the diagonal of a square matrix using matvecs. [ABSTRACT FROM AUTHOR]

Semidefinite programs (SDPs) arising from the Kalman—Yakubovich—Popov (KYP) lemma are frequently encountered in systems robustness analysis, filter design, and other control/signal processing related applications. These programs possess a special structure that can be exploited to construct specialized algorithms that substantially outperform general-purpose SDP solvers. In this paper, a new interior path-following algorithm that utilizes this structure is proposed. The main idea behind the algorithm is a new barrier function for these specially structured SDPs. Convergence of the new algorithm is shown and a measure of the accuracy of suboptimal solutions produced by the algorithm is provided. The algorithm is tested in numerical experiments and the results indicate that the new algorithm is indeed favorable against general-purpose SDP solvers in many circumstances. [ABSTRACT FROM AUTHOR]

In the first part of this paper we develop a theory for image restoration with a learned regularizer that is analogous to that of Meyer's geometric characterization of solutions of the classical variational method of Rudin-Osher-Fatemi (ROF). The learned regularizer we use is a Kantorovich potential for an optimal transport problem of mapping a distribution of noisy images onto clean ones, as first proposed by Lunz, \" Oktem, and Sch\"onlieb. We show that the effect of their restoration method on the distribution of the images is an explicit Euler discretization of a gradient flow on probability space, while our variational problem, dubbed Wasserstein ROF (WROF), is the corresponding implicit Euler discretization. We obtain our geometric characterization of the solution in this learned regularizer setting by first proving a much more general convex analysis theorem for variational problems having solutions characterized by projections. We then use optimal transport arguments to obtain the corresponding theorem for WROF from this general result, as well as a natural decomposition of a transport map into large scale "features" and small scale "details," where scale refers to the magnitude of the transport distance. In the second part of the paper we leverage our theory for restoration with learned regularizers to analyze two algorithms which iterate WROF. We refer to these as iterative regularization and multiscale transport. For the former we obtain a proof of convergence to the clean data. For the latter we produce successive approximations to the target distribution that match it up to finer and finer scales. These two algorithms are in complete analogy to well-known effective methods based on ROF for iterative denoising, respectively hierarchical image decomposition. We also obtain an analogue of the Tadmor-Nezzar-Vese energy identity, which decomposes the Wasserstein 2 distance between two measures into a sum of nonnegative terms that correspond to transport costs at different scales. [ABSTRACT FROM AUTHOR]

This is the first paper in a series whose goal is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial-time algorithm that determines if a special kind of precoloring of a P6-free graph has a precoloring extension, and constructs such an extension if one exists. Combined with the main result of the second paper of the series, this gives a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This is the second paper in a series of two. The goal of the series is to give a polynomial-time algorithm for the 4-coloring problem and the 4-precoloring extension problem restricted to the class of graphs with no induced six-vertex path, thus proving a conjecture of Huang. Combined with previously known results, this completes the classification of the complexity of the 4-coloring problem for graphs with a connected forbidden induced subgraph. In this paper we give a polynomial time-algorithm that starts with a 4-precoloring of a graph with no induced six-vertex path and outputs a polynomial-sized collection of so-called excellent precolorings. Excellent precolorings are easier to handle than general ones, and, in addition, in order to determine whether the initial precoloring can be extended to the whole graph, it is enough to answer the same question for each of the excellent precolorings in the collection. The first paper in the series deals with excellent precolorings, thus providing a complete solution to the problem. [ABSTRACT FROM AUTHOR]

This paper presents an interior point method for pure state and mixed-constraint optimal control problems for dynamics, mixed constraints, and cost function all affine in the control variable. This method relies on resolving a sequence of two-point boundary value problems of differential and algebraic equations. This paper establishes a convergence result for primal and dual variables of the optimal control problem. A primal and a primal-dual solving algorithm are presented, and a challenging numerical example is treated for illustration. [ABSTRACT FROM AUTHOR]

Image processing on surfaces has gotten increasing interest in recent years, and denoising is a basic problem in image processing. In this paper, we extend non-Lipschitz variational methods for 2D image denoising, including TVp, to image denoising on surfaces. We establish a lower bound for nonzero gradients of the recovered image, implying the advantage of the models in recovering piecewise constant images. A new iteratively reweighted least squares algorithm with the thresholding and support shrinking strategy is proposed. The global convergence of the algorithm is established under the assumption that the object function is a Kurdyka-Łojasiewicz function. Numerical examples are given to show good performance of the algorithm. [ABSTRACT FROM AUTHOR]

Large-scale linear systems, Ax = b, frequently arise in practice and demand effective iterative solvers. Often, these systems are noisy due to operational errors or faulty data-collection processes. In the past decade, the randomized Kaczmarz algorithm (RK) has been studied extensively as an efficient iterative solver for such systems. However, the convergence study of RK in the noisy regime is limited and considers measurement noise in the right-hand side vector, b. Unfortunately, in practice, that is not always the case; the coefficient matrix A can also be noisy. In this paper, we analyze the convergence of RK for doubly noisy linear systems, i.e., when the coefficient matrix, A, has additive or multiplicative noise, and b is also noisy. In our analyses, the quantity R = ||Æ ||²||Ã||²F influences the convergence of RK, where A represents a noisy version of A. We claim that our analysis is robust and realistically applicable, as we do not require information about the noiseless coefficient matrix, A, and by considering different conditions on noise, we can control the convergence of RK. We perform numerical experiments to substantiate our theoretical findings. [ABSTRACT FROM AUTHOR]

Hierarchical matrices are dense but data-sparse matrices that use low-rank factorizations of suitable submatrices to reduce the storage and computational cost to linear-polylogarithmic complexity. In this paper, we propose a new approach to efficiently compute QR factorizations in the hierarchical matrix format based on block Householder transformations. To prevent unnecessarily high ranks in the resulting factors and to increase speed and accuracy, the algorithm meticulously tracks for which intermediate results low-rank factorizations are available. We also use a special storage scheme for the block Householder reflector to further reduce computational and storage costs. Numerical tests for two- and three-dimensional Laplacian boundary element matrices, different radial basis function kernel matrices, and matrices of typical hierarchical matrix structures but filled with random entries illustrate the performance of the new algorithm in comparison to some other QR algorithms for hierarchical matrices from the literature. [ABSTRACT FROM AUTHOR]

Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These functions play a fundamental role in algebra, artificial intelligence, combinatorics, computer science, database theory, and logic. In the present paper, we introduce the subclass of hypergraph Horn functions that generalizes matroids and equivalence relations. We provide multiple characterizations of hypergraph Horn functions in terms of implicate-duality and the closure operator, which are, respectively, regarded as generalizations of matroid duality and the Mac Lane-Steinitz exchange property of matroid closure. We also study algorithmic issues on hypergraph Horn functions and show that the recognition problem (i.e., deciding if a given definite Horn CNF represents a hypergraph Horn function) and key realization (i.e., deciding if a given hypergraph is realized as a key set by a hypergraph Horn function) can be done in polynomial time, while implicate sets can be generated with polynomial delay. [ABSTRACT FROM AUTHOR]

In this paper, we study zeroth-order algorithms for nonconvex-concave minimax problems, which have attracted much attention in machine learning, signal processing, and many other fields in recent years. We propose a zeroth-order alternating randomized gradient projection (ZO-AGP) algorithm for smooth nonconvex-concave minimax problems; its iteration complexity to obtain an varepsilon -stationary point is bounded by crO (\varepsilon 4), and the number of function value estimates is bounded by scrO (dx + dy) per iteration. Moreover, we propose a zeroth-order block alternating randomized proximal gradient algorithm (ZO-BAPG) for solving blockwise nonsmooth nonconvexconcave minimax optimization problems; its iteration complexity to obtain an varepsilon -stationary point is bounded by scrO (varepsilon 4), and the number of function value estimates per iteration is bounded by O (Kdx +dy). To the best of our knowledge, this is the first time zeroth-order algorithms with iteration complexity guarantee are developed for solving both general smooth and blockwise nonsmooth nonconvex-concave minimax problems. Numerical results on the data poisoning attack problem and the distributed nonconvex sparse principal component analysis problem validate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing approaches ranging from direct transcription to hybrid quantum- classical approaches rooted in existing optimization algorithms. While it is widely acknowledged that quantum computers should augment classical computers, rather than replace them entirely, comparatively little attention has been directed toward deriving analytical characterizations of their interactions. In this paper, we present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs (MBQP) via Ising solvers. By leveraging an existing completely positive reformulation of MBQPs, as well as a new strong-duality result, we show the exactness of the dual problem over the cone of copositive matrices, thus allowing the resulting reformulation to inherit the straightforward analysis of convex optimization. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm. Using existing complexity results for convex cutting-plane algorithms, we deduce that the classical portion of this hybrid framework is guaranteed to be polynomial time. This suggests that when applied to NP-hard problems, the complexity of the solution is shifted onto the subroutine handled by the Ising solver. [ABSTRACT FROM AUTHOR]

In this paper we develop and analyze a variational data assimilation method with efficient decoupled iterative numerical algorithms for the Stokes–Darcy equations with the Beavers–Joseph interface condition. By using Tikhonov regularization and formulating the variational data assimilation into an optimization problem, we establish the existence, uniqueness, and stability of the optimal solution. Based on the weak formulation of the Stokes–Darcy equations, the Lagrange multiplier rule is utilized to derive the first order optimality system for both the continuous and discrete variational data assimilation problems, where the discrete data assimilation is based on a finite element discretization in space and the backward Euler scheme in time. By rescaling the optimality system and then analyzing its corresponding bilinear forms, we prove the optimal finite element convergence rate with special attention paid to recovering uncertainties missed in the optimality system. To solve the discrete optimality system efficiently, three decoupled iterative algorithms are proposed to address the computational cost for both well-conditioned and ill-conditioned variational data assimilation problems, respectively. Finally, numerical results are provided to validate the proposed methods. [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 consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-conjugate gradient (Newton-CG) method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method in [C. W. Royer, M. O'Neill, and S. J. Wright, Math. Program., 180 (2020), pp. 451-488]. We then propose a Newton-CG based augmented Lagrangian (AL) method for finding an approximate SOSP of nonconvex equality constrained optimization, in which the proposed Newton-CG method is used as a subproblem solver. We show that under a generalized linear independence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of O(ε7/peration complexity of O(ε7/2 min\{ n, ε3/4\}) for finding an (ε, ε)-SOSP of nonconvex equality constrained optimization with high probability, which are significantly better than the ones achieved by the proximal AL method in [Y. Xie and S. J. Wright, J. Sci. Comput., 86 (2021), pp. 1-30]. In addition, we show that it has a total inner iteration complexity of O(ε11/2) and an operation complexity of O(ε11/2 min\{ n, ε5/4\}) when the GLICQ does not hold. To the best of our knowledge, all the complexity results obtained in this paper are new for finding an approximate SOSP of nonconvex equality constrained optimization with high probability. Preliminary numerical results also demonstrate the superiority of our proposed methods over the other competing algorithms. [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 work, a method for obtaining pixelwise error bounds in Bayesian regularization of inverse imaging problems is introduced. The proposed method employs estimates of the posterior variance together with techniques from conformal prediction in order to obtain coverage guarantees for the error bounds, without making any assumption on the underlying data distribution. It is generally applicable to Bayesian regularization approaches, independent, e.g., of the concrete choice of the prior. Furthermore, the coverage guarantees can also be obtained in case only approximate sampling from the posterior is possible. With this in particular, the proposed framework is able to incorporate any learned prior in a black-box manner. Guaranteed coverage without assumptions on the underlying distributions is only achievable since the magnitude of the error bounds is, in general, unknown in advance. Nevertheless, experiments with multiple regularization approaches presented in the paper confirm that, in practice, the obtained error bounds are rather tight. For realizing the numerical experiments, a novel primal-dual Langevin algorithm for sampling from nonsmooth distributions is also introduced in this work, showing promising results in practice. While a proof of convergence for this primal-dual algorithm is still open, the theoretical guarantees of the proposed method do not require a guaranteed convergence of the sampling algorithm. [ABSTRACT FROM AUTHOR]

The Euler elastica (EE) model with surface curvature can generate artifact-free results compared with the traditional total variation regularization model in image processing. However, strong nonlinearity and singularity due to the curvature term in the EE model pose a great challenge for one to design fast and stable algorithms for the EE model. In this paper, we propose a new, fast, hybrid alternating minimization (HALM) algorithm for the EE model based on a bilinear decomposition of the gradient of the underlying image and prove the global convergence of the minimizing sequence generated by the algorithm under mild conditions. The HALM algorithm comprises three subminimization problems and each is either solved in the closed form or approximated by fast solvers, making the new algorithm highly accurate and efficient. We also discuss the extension of the HALM strategy to deal with general curvature-based variational models, especially with a Lipschitz smooth functional of the curvature. A host of numerical experiments are conducted to show that the new algorithm produces good results with much-improved efficiency compared to other state-of-the-art algorithms for the EE model. As one of the benchmarks, we show that the average running time of the HALM algorithm is at most one-quarter of that of the fast operator-splitting-based Deng--Glowinski--Tai algorithm. [ABSTRACT FROM AUTHOR]

The constrained pressure residual (CPR) algorithm is a family of well-known and industry-standard preconditioners for large-scale reservoir simulation. The CPR algorithm is a twostage preconditioner to deal with different blocks stage-by-stage, and is often able to effectively improve the robustness behavior and the convergence speed of linear iterations. Nonetheless, as a linear preconditioner, it is hard for the traditional CPR method to be capable of action at the nonlinear level for effectively solving large sparse nonlinear systems of equations with high nonlinearity. In this paper, we present and study the extension of this linear method to the nonlinearly CPR (NCPR) case for solving fractured reservoir problems, to deal with the difficulty of the slow convergence or stagnation from the nonlinear level. In the proposed nonlinear preconditioning, a subspace nonlinear block system is first built and solved to remove the unbalanced nonlinearities of the pressure and the saturation fields, and the fast convergence can then be restored when a variant of semismooth Newton methods is called after the subspace nonlinear block system is solved. Experiments on two or three dimensional porous media applications are presented to demonstrate the applicability and parallel scalability of the aforementioned NCPR method. We also show that the proposed algorithm is superior to the commonly used nonlinear algorithm in terms of the robustness and the positivity-preserving property. [ABSTRACT FROM AUTHOR]

Structure-preserving doubling algorithms (SDAs) are efficient algorithms for solving Riccati-type matrix equations. However, breakdowns may occur in SDAs. To remedy this drawback, in this paper, we first introduce Ω -symplectic forms (Ω -SFs), consisting of symplectic matrix pairs with a Hermitian parametric matrix Ω. Based on Ω -SFs, we develop modified SDAs (MSDAs) for solving the associated Riccati-type equations. MSDAs generate sequences of symplectic matrix pairs in Ω -SFs and prevent breakdowns by employing a reasonably selected Hermitian matrix Ω. In practical implementations, we show that the Hermitian matrix Ω in MSDAs can be chosen as a real diagonal matrix that can reduce the computational complexity. The numerical results demonstrate a significant improvement in the accuracy of the solutions by MSDAs. [ABSTRACT FROM AUTHOR]

Proximal mappings are essential in splitting algorithms for both convex and noncon-vex optimization. In this paper, we show that proximal mappings of every prox-bounded function are nonexpansive if and only if they are firmly nonexpansive if and only if they are averaged if and only if the function is convex. Lipschitz proximal mappings of prox-bounded functions are also characterized via hypoconvex or strongly convex functions. Our results generalize a recent result due to Rockafellar [ABSTRACT FROM AUTHOR]

Given closed convex sets Ci, i=1, ... l, and some nonzero linear maps Ai, i=1, ... l, of suitable dimensions, the multiset split feasibility problem aims at finding a point in ... based on computing projections onto Ci and multiplications by Ai and AiT. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto ...; we refer to this problem as the best approximation problem in multiset split feasibility settings (BA-MSF). We adapt the Dykstra's projection algorithm, which is classical for solving the BA-MSF in the special case when all Ai - I, to solve the general BA-MSF. Our Dykstra-type projection algorithm is derived by applying (proximal) coordinate gradient descent to the Lagrange dual problem, and it only requires computing projections onto Ci and multiplications by Ai and AiT in each iteration. Under a standard relative interior condition and a genericity assumption on the point we need to project, we show that the dual objective satisfies the Kurdyka-Łojasiewicz property with an explicitly computable exponent on a neighborhood of the (typically unbounded) dual solution set when each Ci is C1,α.-cone reducible for some α∈ (0,1]: this class of sets covers the class of C²-cone reducible sets, which include all polyhedrons, second-order cone, and the cone of positive semidefinite matrices as special cases. Using this, explicit convergence rate (linear or sublinear) of the sequence generated by the Dykstra-type projection algorithm is derived. Concrete examples are constructed to illustrate the necessity of some of our assumptions. [ABSTRACT FROM AUTHOR]

This paper proposes a path-based approach for the minimization of a continuously differentiable function over sparse symmetric sets, which is a hard problem that exhibits a restrictiveness-hierarchy of necessary optimality conditions. To achieve the more restrictive conditions in the hierarchy, state-of-the-art algorithms require a support optimization oracle that must exactly solve the problem in smaller dimensions. The path-based approach developed in this study produces a path-based optimality condition, which is placed well in the restrictiveness-hierarchy, and a method to achieve it that does not require a support optimization oracle and, moreover, is projection-free. In the development process, new results are derived for the regularized linear minimization problem over sparse symmetric sets, which give additional means to identify optimal solutions for convex and concave objective functions. We complement our results with numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, we have studied a decomposition method for solving a class of non-convex two-stage stochastic programs, where both the objective and constraints of the second-stage problem are nonlinearly parameterized by the first-stage variables. Due to the failure of the Clarke regularity of the resulting nonconvex recourse function, classical decomposition approaches such as Benders decomposition and (augmented) Lagrangian-based algorithms cannot be directly generalized to solve such models. By exploring an implicitly convex-concave structure of the recourse function, we introduce a novel decomposition framework based on the so-called partial Moreau envelope. The algorithm successively generates strongly convex quadratic approximations of the recourse function based on the solutions of the second-stage convex subproblems and adds them to the first-stage mas-ter problem. Convergence has been established for both a fixed number of scenarios and a sequential internal sampling strategy. Numerical experiments are conducted to demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we consider a class of structured nonsmooth difference-of-convex (DC) minimization in which the first convex component is the sum of a smooth and a nonsmooth function, while the second convex component is the supremum of finitely many convex smooth functions. The existing methods for this problem usually have weak convergence guarantees or need to solve lots of subproblems per iteration. Due to this, we propose hybrid algorithms for solving this problem in which we first compute approximate critical points and then check whether these points are approximate D-stationary points. Under suitable conditions, we prove that there exists a subsequence of iterates of which every accumulation point is a D-stationary point. Some preliminary numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms. [ABSTRACT FROM AUTHOR]

In the Bin Packing problem one is given n items with weights w(1),. . . ,w(n) and m bins with capacities c1, . . ., cm. The goal is to partition the items into sets S1, . . . ,Sm such that w(Sjmn) notation omits factors polynomial in the input size). In this paper, we show that for every m N there exists a constant Σm > 0 such that an instance of Bin Packing with m bins can be solved in O (2(1 y m)n) randomized time. Before our work, such improved algorithms were not known even for m= 4. A key step in our approach is the following new result in Littlewood--Offord theory on the additive combinatorics of subset Σ: For every γ > 0 there exists an >0 such that if | { X n{ 1, . . . ,n}: w(X) =v} | 2(1)n for some v, then { w(X) :X { 1, . . . ,n\} | &#947n. [ABSTRACT FROM AUTHOR]

We consider the problem of reconstructing one-dimensional point sources from their Fourier measurements in a bounded interval [\Omega, \Omega]. This problem is known to be challenging in the regime where the spacing of the sources is below the Rayleigh length \pi \Omega. In this paper, we propose a superresolution algorithm, called iterative focusing-localization and filtering, to resolve closely spaced point sources from their multiple measurements that are obtained by using multiple unknown illumination patterns. The new proposed algorithm has a distinct feature in that it reconstructs the point sources one by one in an iterative manner and hence requires no prior information about the source numbers. The new feature also allows for a subsampling strategy that can reconstruct sources using small-sized Hankel matrices and thus circumvent the computation of singular-value decomposition for large matrices as in the usual subspace methods. In addition, the algorithm can be paralleled. A theoretical analysis of the methods behind the algorithm is also provided. The derived results imply a phase transition phenomenon in the reconstruction of source locations which is confirmed in the numerical experiment. Numerical results show that the algorithm can achieve a stable reconstruction for point sources with a minimum separation distance that is close to the theoretical limit. The efficiency and robustness of the algorithm have also been tested. This algorithm can be generalized to higher dimensions. [ABSTRACT FROM AUTHOR]

Stochastic Parareal (SParareal) is a probabilistic variant of the popular parallel-in-time algorithm known as Parareal. Similarly to Parareal, it combines fine- and coarse-grained solutions to an ODE using a predictor-corrector (PC) scheme. The key difference is that carefully chosen random perturbations are added to the PC to try to accelerate the location of a stochastic solution to the ODE. In this paper, we derive superlinear and linear mean-square error bounds for SParareal applied to nonlinear systems of ODEs using different types of perturbations. We illustrate these bounds numerically on a linear system of ODEs and a scalar nonlinear ODE, showing a good match between theory and numerics. [ABSTRACT FROM AUTHOR]

We propose in this paper a new minimization algorithm based on a slightly modified version of the scalar auxialiary variable (SAV) approach coupled with a relaxation step and an adaptive strategy. It enjoys several distinct advantages over popular gradient based methods: (i) it is unconditionally energy diminishing with a modified energy which is intrinsically related to the original energy, and thus no parameter tuning is needed for stability; (ii) it allows the use of large step-sizes which can effectively accelerate the convergence rate. We also present a convergence analysis for some SAV based algorithms, which include our new algorithm without the relaxation step as a special case. We apply our new algorithm to several illustrative and benchmark problems and compare its performance with several popular gradient based methods. The numerical results indicate that the new algorithm is very robust, and its adaptive version usually converges significantly faster than those popular gradient decent based methods. [ABSTRACT FROM AUTHOR]

Policy gradient algorithms have been widely applied to Markov decision processes and reinforcement learning problems in recent years. Regularization with various entropy functions is often used to encourage exploration and improve stability. This paper proposes an approximate Newton method for the policy gradient algorithm with entropy regularization. In the case of Shannon entropy, the resulting algorithm reproduces the natural policy gradient algorithm. For other entropy functions, this method results in brand-new policy gradient algorithms. We prove that all these algorithms enjoy Newton-type quadratic convergence and that the corresponding gradient flow converges globally to the optimal solution. We use synthetic and industrial-scale examples to demonstrate that the proposed approximate Newton method typically converges in single-digit iterations, often orders of magnitude faster than other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

Symmetries of a set are linear transformations that map the set to itself. A fundamental domain of a symmetric set is a subset that contains at least one representative from each of the symmetric equivalence classes (orbits) in the set. This paper contributes a novel polynomial algorithm for constructing minimal polytopic fundamental domains of polytopic sets. Our algorithm is applicable for generic linear symmetries of the set and has linear complexity in the number of facets and dimension of the symmetric polytope, e.g., the feasible region of an optimization problem. In addition, this paper contributes a novel polynomial algorithm for mapping an element of the polytope to its representative in the fundamental domain. The algorithms are demonstrated in four examples--two illustrative and two practical. In the first practical example, we show that a minimal fundamental domain of the hypercube under the symmetric group is the set of points with sorted elements. In the second practical example, we show how the construction algorithm can be applied to the max-cut problem. [ABSTRACT FROM AUTHOR]

Computational and mathematical models are research subjects for solving engineering, computer science, and computer vision problems. Image preprocessing usually needs to efficiently compute polygons related to some previously delimited region of interest. Most of the solved problems are limited to the search for some type of polygon with k sides (triangles, rectangles, squares, etc.) with maximum area, maximum perimeter, or similar. This paper presents a generic algorithm that computes in O(n5k) computational time the polygon of any number of sides (any simple k-gon) inscribed in a region of interest (in any closed contour without restrictions). The polygon obtained fulfills the requirements specified by the user: maximum area or perimeter or minimum area or perimeter. No previous work has been proposed to obtain any k-gon inscribed in any unconstrained contour. The algorithms and mathematical models are presented and explained, and the source code is available in a GitHub repository for research purposes. [ABSTRACT FROM AUTHOR]

The paper deals with stochastic difference-of-convex-functions (DC) programs, that is, optimization problems whose cost function is a sum of a lower semicontinuous DC function and the expectation of a stochastic DC function with respect to a probability distribution. This class of nonsmooth and nonconvex stochastic optimization problems plays a central role in many practical applications. Although there are many contributions in the context of convex and/or smooth stochastic optimization, algorithms dealing with nonconvex and nonsmooth programs remain rare. In deterministic optimization literature, the DC algorithm (DCA) is recognized to be one of the few algorithms able to effectively solve nonconvex and nonsmooth optimization problems. The main purpose of this paper is to present some new stochastic DCAs for solving stochastic DC programs. The convergence analysis of the proposed algorithms is carefully studied, and numerical experiments are conducted to justify the algorithms' behaviors. [ABSTRACT FROM AUTHOR]

Conventional inversion of the discrete Fourier transform (DFT) requires all DFT coefficients to be known. When the DFT coefficients of a rasterized image (represented as a matrix) are known only within a pass band, the original matrix cannot be uniquely recovered. In many cases of practical importance, the matrix is binary and its elements can be reduced to either 0 or 1. This is the case, for example, for the commonly used QR codes. The a priori information that the matrix is binary can compensate for the missing high-frequency DFT coefficients and restore uniqueness of image recovery. This paper addresses, both theoretically and numerically, the problem of recovery of blurred images without any known structure whose high-frequency DFT coefficients have been irreversibly lost by utilizing the binarity constraint. We investigate theoretically the smallest band limit for which unique recovery of a generic binary matrix is still possible. Uniqueness results are proved for images of sizes N1×N2, N1×N1, and N\α 1×Nα 1, where N¹\not =N2 are prime numbers and\alpha >1 an integer. Inversion algorithms are proposed for recovering the matrix from its band-limited (blurred) version. The algorithms combine integer linear programming methods with lattice basis reduction techniques and significantly outperform naive implementations. The algorithm efficiently and reliably reconstructs severely blurred 29×29 binary matrices with only 11×11 = 121 DFT coefficients. [ABSTRACT FROM AUTHOR]

The stretch energy is a fully nonlinear energy functional that has been applied to the numerical computation of area-preserving mappings. However, this approach lacks theoretical support and the analysis is complicated due to the full nonlinearity of the functional. In this paper, we establish a theoretical foundation of stretch energy minimization (SEM) for the computation of area-preserving mappings: the sufficient and necessary conditions for the energy minimizers are mappings being area-preserving. In addition, we derive a neat gradient formula of the functional and develop the associated line search gradient descent method of SEM with theoretically guaranteed convergence. Also, a simple post-processing technique is developed to guarantee the bijectivity of produced mappings. Furthermore, we generalized the theoretical results to the stretch energy for arbitrary area measures and the balanced energy so that the mass-preserving and distortion-balancing mappings can also be computed by minimizing the generalized stretch energy and the balanced energy, respectively. Numerical experiments and comparisons to another state-of-the-art algorithm are demonstrated to validate the effectiveness, accuracy, and robustness of SEM for computing area-preserving mappings. [ABSTRACT FROM AUTHOR]

This paper presents an extension of the Adaptive Antoulas-Anderson (AAA) algorithm for rational modeling. Specifically, our new stable multi-input multi-output AAA (smiAAA) algorithm builds rational approximations of multi-input signals with a common set of stable poles. A new methodology is presented for iteratively enforcing the stability constraint on the poles. We demonstrate the strengths of this approach compared to the stability enforcement in the FastAAA algorithm. Results using the smiAAA algorithm are compared with the commonly used Vector Fitting algorithm and the more recently published Rational Krylov fitting (RKFIT) algorithm. The Vector Fitting and RKFIT algorithms both require the user to input the number of poles to use in the approximations. If the final approximation is not accurate enough, the user must restart the Vector Fitting or RKFIT algorithm with a larger number of poles and/or a new starting location for the poles. In contrast, the smiAAA algorithm is designed to allow the user to simply input the desired accuracy of the approximations, and the necessary number of poles is detected automatically. This permits users to produce approximations of a desired accuracy with no knowledge about the underlying order of the system being approximated, preventing the algorithm from ever needing to be rerun. An additional feature for preventing extraneous poles from being returned by the AAA algorithm is also discussed. The cause of these extraneous poles is efficiently detected and removed by our presented methodology. The examples presented demonstrate that the smiAAA algorithm can efficiently produce approximations of similar or better accuracy than the Vector Fitting and RKFIT algorithms while requiring less input from the user. [ABSTRACT FROM AUTHOR]

Motivated by an application in cancer genomics, Hajirasouliha and Raphael [Proceedings of the 14th International Workshop on Algorithms in Bioinformatics, 2014, pp. 354-367] proposed the split-row problem (SR). In this problem, an m\times n binary matrix M is given. A split-row operation on M is defined as replacing a row r by k > 1 rows r(1), r(2), . . ., r(k) whose bitwise OR is equal to r. The cost of the operation is the number of additional rows induced, that is, k 1. The goal is to find a sequence of split-row operations that transforms M into a matrix corresponding to a perfect phylogeny and the total cost is minimized. Recently, Hujdurovi\'c et al. [ACM Trans. Algorithms, 14 (2018), 26] proved the APX-hardness of SR and presented efficient exact and approximation algorithms. The parameterized study of SR was left as a direction for future work. Let\varepsilon (M) denote the minimum total cost. This paper gives an O*(2min(n,2x(M))-time exact algorithm for SR. This result indicates that SR is fixed-parameter tractable when parameterized by E (M). In addition, in the worst case, our algorithm requires O* (2n) time, significantly improving the previous upper bound of O\ast (nn). Hujdurovi\'c et al.'s exact algorithm can be modified to solve a variant of SR, called the distinct split-row problem (DSR). Our algorithm can be adapted to this variant as well. In addition, our algorithms can be extended to solve SR and DSR with the following additional constraint: only the rows in a given subset are allowed to be split. [ABSTRACT FROM AUTHOR]

For many algorithmic problems on graphs of treewidth t, a standard dynamic programming approach gives algorithms with time and space complexity 2O(t)\cdot nO(1). It turns out that when one considers the more restrictive parameter treedepth, it is often the case that a variation of this technique can be used to reduce the space complexity to polynomial, while retaining time complexity of the form 2O(d)\cdot nO(1), where d is the treedepth. This transfer of methodology is, however, far from automatic. For instance, for problems with connectivity constraints, standard dynamic programming techniques give algorithms with time and space complexity 2O(t)...nO(1) on graphs of treewidth t, but it is not clear how to convert them into time-efficient polynomial space algorithms for graphs of low treedepth. Cygan et al. [ACM Trans. Algorithms, 18 (2022), 17] introduced the Cut\&Count technique and showed that a certain class of problems with connectivity constraints can be solved in time and space complexity 2O(t) · nO(1). Recently, Hegerfeld and Kratsch (STACS'20) showed that, for some of those problems, the Cut\&Count technique can be also applied in the setting of treedepth, and it gives algorithms with running time 2O(d) · nO(1) and polynomial space usage. However, several important problems eluded such a treatment, with the most prominent examples being Hamiltonian Cycle and Longest Path. In this paper, we clarify the situation by showing that Hamiltonian cycle, Hamiltonian Path, Long Cycle, Long Path, and Min Cycle Cover all admit 5d · nO(1)-time and polynomial space algorithms on graphs of treedepth d. The algorithms are randomized Monte Carlo with only false negatives. [ABSTRACT FROM AUTHOR]

Nonlinear filtering is fundamental to many engineering problems, as it involves inferring the state of a system given complicated dynamics and noisy observations. Some approaches to nonlinear filtering use the analysis of the underlying PDE or stochastic PDE governing the evolution of the posterior probability distribution over time, one approach, in particular, being the Yau-Yau method. In this paper, we give a maximum a posteriori (MAP) framework for the Yau-Yau method. Furthermore, we propose convex filtering, intermediate between linear and nonlinear filtering, which gives criteria under which the posterior preserves log-concavity. The key tool from the PDE is a result from Korevaar, giving criteria under which a quasilinear parabolic PDE preserves convexity. A bridge between the MAP estimator and the structure of the posterior is explained. Finally, we propose a novel numerical method based on iteration and apply this method to a tracking problem. [ABSTRACT FROM AUTHOR]

In this paper we consider large-scale composite optimization problems having the objective function formed as a sum of two terms (possibly nonconvex); one has a (block) coordinatewise Lipschitz continuous gradient and the other is differentiable but nonseparable. Under these general settings we derive and analyze two new coordinate descent methods. The first algorithm, referred to as the coordinate proximal gradient method, considers the composite form of the objective function, while the other algorithm disregards the composite form of the objective and uses the partial gradient of the full objective, yielding a coordinate gradient descent scheme with novel adaptive stepsize rules. We prove that these new stepsize rules make the coordinate gradient scheme a descent method, provided that additional assumptions hold for the second term in the objective function. We present a complete worst-case complexity analysis for these two new methods in both convex and nonconvex settings, provided that the (block) coordinates are chosen random or cyclic. Preliminary numerical results also confirm the efficiency of our two algorithms for practical problems. [ABSTRACT FROM AUTHOR]

An adaptive regularization algorithm for unconstrained nonconvex optimization is presented in which the objective function is never evaluated but only derivatives are used. This algorithm belongs to the class of adaptive regularization methods, for which optimal worst-case complexity results are known for the standard framework where the objective function is evaluated. It is shown in this paper that these excellent complexity bounds are also valid for the new algorithm despite the fact that significantly less information is used. In particular, it is shown that if derivatives of degree one to p are used, the algorithm will find an ε 1-approximate first-order minimizer in at most O(ε (p+1)/p 1 ) iterations and an (ε 1, ε 2)-approximate second-order minimizer in at most O(max[ε¹ (p+1)/p 1, ε (p+1)/(p 1) 2 ]) iterations. As a special case, the new algorithm using first and second derivatives, when applied to functions with Lipschitz continuous Hessian, will find an iterate xk at which the gradient's norm is less than ε 1 in at most O(ε1 3/2) iterations. [ABSTRACT FROM AUTHOR]

Packing and covering semidefinite programs (SDPs) appear in natural relaxations of many combinatorial optimization problems as well as a number of other applications. Recently, several techniques were proposed, which utilize the particular structure of this class of problems, to obtain more efficient algorithms than those offered by general SDP solvers. For certain applications, such as those described in this paper, it may be desirable to obtain sparse dual solutions, i.e., those with support size (almost) independent of the number of primal constraints. In this paper, we give an algorithm that finds such solutions, which is an extension of a logarithmic-potential based algorithm of Grigoriadis et al. [SIAM J. Optim. 11 (2001), pp. 1081-1091] for packing/covering linear programs. [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]

Efficient sampling from a high-dimensional Gaussian distribution is an old but high-stakes issue. Vanilla Cholesky samplers imply a computational cost and memory requirements that can rapidly become prohibitive in high dimensions. To tackle these issues, multiple methods have been proposed from different communities ranging from iterative numerical linear algebra to Markov chain Monte Carlo (MCMC) approaches. Surprisingly, no complete review and comparison of these methods has been conducted. This paper aims to review all these approaches by pointing out their differences, close relations, benefits, and limitations. In addition to reviewing the state of the art, this paper proposes a unifying Gaussian simulation framework by deriving a stochastic counterpart of the celebrated proximal point algorithm in optimization. This framework offers a novel and unifying revisiting of most of the existing MCMC approaches while also extending them. Guidelines to choosing the appropriate Gaussian simulation method for a given sampling problem in high dimensions are proposed and illustrated with numerical examples. [ABSTRACT FROM AUTHOR]

Computer implementations of vector orthogonalization algorithms produce a sequence of supposedly orthogonal vectors, but rounding-errors can cause loss of orthogonality and rank. Nevertheless these computational algorithms can be very effective as parts of various methods. We develop a general theory based on the augmented orthogonal matrix developed in that can be applied to any such algorithm. This can be combined with a rounding-error analysis of the algorithm to analyze its finite-precision behavior. We apply this combination to prove that a particular Lanczos tridiagonalization of a Hermitian matrix always computes components for which backward-stable solutions to Ax=b, A=AH, exist. If an appropriate rounding-error analysis is available, the approach can apparently be applied to any computation producing a sequence of supposedly orthogonal n-vectors, where a linear combination of these vectors is intended to approximate some quantity. [ABSTRACT FROM AUTHOR]

In this paper, we present the new "asynchronous truncated multigrid-reduction-intime"" (AT-MGRIT) algorithm for introducing time parallelism to the solution of discretized timedependent problems. The new algorithm is based on the multigrid-reduction-in-time (MGRIT) approach, which, in certain settings, is equivalent to another common multilevel parallel-in-time method, Parareal. In contrast to Parareal and MGRIT that both consider a global temporal grid over the entire time interval on the coarsest level, the AT-MGRIT algorithm uses truncated local time grids on the coarsest level, each grid covering certain temporal subintervals. These local grids can be solved completely in an independent way from each other, which reduces the sequential part of the algorithm and, thus, increases parallelism in the method. Here, we study the effect of using truncated local coarse grids on the convergence of the algorithm, both theoretically and numerically, and show, using challenging nonlinear problems, that the new algorithm consistently outperforms classical Parareal/MGRIT in terms of time to solution. [ABSTRACT FROM AUTHOR]

The tensor-train (TT) decomposition expresses a tensor in a data-sparse format used in molecular simulations, high-order correlation functions, and optimization. In this paper, we propose four parallelizable algorithms that compute the TT format from various tensor inputs: (1) Parallel-TTSVD for traditional format, (2) PSTT and its variants for streaming data, (3) Tucker2TT for Tucker format, and (4) TT-fADI for solutions of Sylvester tensor equations. We provide theoretical guarantees of accuracy, parallelization methods, scaling analysis, and numerical results. For example, for a d-dimension tensor in Rn× ... × n, a two-sided sketching algorithm PSTT2 is shown to have a memory complexity of O (n d/2), improving upon O (nd 1) from previous algorithms. [ABSTRACT FROM AUTHOR]

In this paper we bring together some of the key ideas and methods of two disparate fields of mathematical research, frame theory, and optimal transport, using the methods of the second to answer questions posed in the first. In particular, we construct gradient flows in the Wasserstein space P2(\BbbR d) for a new potential, the tightness potential, which is a modification of the probabilistic frame potential. It is shown that the potential is suited for the application of a gradient descent scheme from optimal transport that can be used as the basis of an algorithm to evolve an existing frame toward a tight probabilistic frame. [ABSTRACT FROM AUTHOR]

In this paper, an efficient ensemble domain decomposition algorithm is proposed for fast solving the fully mixed random Stokes--Darcy model with the physically realistic Beavers--Joseph interface conditions. We utilize the Monte Carlo method for the coupled model with random inputs to derive some deterministic Stokes--Darcy numerical models and use the idea of the ensemble to realize the fast computation of multiple problems. One remarkable feature of the algorithm is that multiple linear systems share a common coefficient matrix in each deterministic numerical model, which significantly reduces the computational cost and achieves comparable accuracy with the traditional methods. Moreover, by domain decomposition, we can decouple the Stokes--Darcy system into two smaller subphysics problems naturally. Both mesh-dependent and mesh-independent convergence rates of the algorithm are rigorously derived by choosing suitable Robin parameters. Optimized Robin parameters are derived and analyzed to accelerate the convergence of the proposed algorithm. Especially, for small hydraulic conductivity in practice, the almost optimal geometric convergence can be obtained by finite element discretization. Finally, two groups of numerical experiments are conducted to validate the exclusive features of the proposed algorithm. [ABSTRACT FROM AUTHOR]