Search

The currently fastest known algorithm for k-SAT is PPSZ, named after its inventors (Paturi et al. in J ACM 52(3):337-364, 2005. ). Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify the analysis of Hertli (in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, Los Alamitos, 2011) for input formulas with multiple satisfying assignments. Second, we show a “lifting result”: if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. In combination this with results by Hansen et al. (in Charikar and Cohen (ed) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019) and Scheder (in 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021), who all prove improved time bounds for Unique-k-SAT, this gives improved bounds for general k-SAT. We also generalize our results to the domain of Constraint Satisfaction Problems, i.e., satisfiability with more than two truth values. [ABSTRACT FROM AUTHOR]

This paper addresses the challenging task of guide wire navigation in cardiovascular interventions, focusing on the parameter estimation of a guide wire system using Ensemble Kalman Inversion (EKI) with a subsampling technique. The EKI uses an ensemble of particles to estimate the unknown quantities. However, since the data misfit has to be computed for each particle in each iteration, the EKI may become computationally infeasible in the case of high-dimensional data, e.g. high-resolution images. This issue can been addressed by randomised algorithms that utilize only a random subset of the data in each iteration. We introduce and analyse a subsampling technique for the EKI, which is based on a continuous-time representation of stochastic gradient methods and apply it to on the parameter estimation of our guide wire system. Numerical experiments with real data from a simplified test setting demonstrate the potential of the method. [ABSTRACT FROM AUTHOR]

We propose a robust randomized indicator method for the reliable detection of eigenvalue existence within an interval for symmetric matrices A. An indicator tells the eigenvalue existence based on some statistical norm estimators for a spectral projector. Previous work on eigenvalue indicators relies on a threshold which is empirically chosen, thus often resulting in under or over detection. In this paper, we use rigorous statistical analysis to guide the design of a robust indicator. Multiple randomized estimators for a contour integral operator in terms of A are analyzed. In particular, when A has eigenvalues inside a given interval, we show that the failure probability (for the estimators to return very small estimates) is extremely low. This enables to design a robust rejection indicator based on the control of the failure probability. We also give a prototype framework to illustrate how the indicator method may be applied numerically for eigenvalue detection and may potentially serve as a new way to design randomized symmetric eigenvalue solvers. Unlike previous indicator methods that only detect eigenvalue existence, the framework also provides a way to find eigenvectors with little extra cost by reusing computations from indicator evaluations. Extensive numerical tests show the reliability of the eigenvalue detection in multiple aspects. [ABSTRACT FROM AUTHOR]

The optimal transport (OT) problem can be reduced to a linear programming (LP) problem through discretization. In this paper, we introduced the random block coordinate descent (RBCD) methods to directly solve this LP problem. Our approach involves restricting the potentially large-scale optimization problem to small LP subproblems constructed via randomly chosen working sets. By using a random Gauss-Southwell-q rule to select these working sets, we equip the vanilla version of ( RBCD 0 ) with almost sure convergence and a linear convergence rate to solve general standard LP problems. To further improve the efficiency of the ( RBCD 0 ) method, we explore the special structure of constraints in the OT problems and leverage the theory of linear systems to propose several approaches for refining the random working set selection and accelerating the vanilla method. Inexact versions of the RBCD methods are also discussed. Our preliminary numerical experiments demonstrate that the accelerated random block coordinate descent (ARBCD) method compares well with other solvers including stabilized Sinkhorn’s algorithm when seeking solutions with relatively high accuracy, and offers the advantage of saving memory. [ABSTRACT FROM AUTHOR]

In this paper we consider multi-objective optimization problems over a box. Several computational approaches to solve these problems have been proposed in the literature, that broadly fall into two main classes: evolutionary methods, which are usually very good at exploring the feasible region and retrieving good solutions even in the nonconvex case, and descent methods, which excel in efficiently approximating good quality solutions. In this paper, first we confirm, through numerical experiments, the advantages and disadvantages of these approaches. Then we propose a new method which combines the good features of both. The resulting algorithm, which we call Non-dominated Sorting Memetic Algorithm, besides enjoying interesting theoretical properties, excels in all of the numerical tests we performed on several, widely employed, test functions. [ABSTRACT FROM AUTHOR]

The Feedback Vertex Set problem is undoubtedly one of the most well-studied problems in Parameterized Complexity. In this problem, given an undirected graph G and a non-negative integer k, the objective is to test whether there exists a subset S ⊆ V (G) of size at most k such that G - S is a forest. After a long line of improvement, recently, Li and Nederlof [TALG, 2022] designed a randomized algorithm for the problem running in time O ⋆ (2. 7 k) ∗ . In the Parameterized Complexity literature, several problems around Feedback Vertex Set have been studied. Some of these include Independent Feedback Vertex Set (where the set S should be an independent set in G), Almost Forest Deletion and Pseudoforest Deletion. In Pseudoforest Deletion, each connected component in G - S has at most one cycle in it. However, in Almost Forest Deletion, the input is a graph G and non-negative integers k , ℓ ∈ N , and the objective is to test whether there exists a vertex subset S of size at most k, such that G - S is ℓ edges away from a forest. In this paper, using the methodology of Li and Nederlof [TALG, 2022], we obtain the current fastest algorithms for all these problems. In particular we obtain the following randomized algorithms. Independent Feedback Vertex Set can be solved in time O ⋆ (2. 7 k) . Pseudo Forest Deletion can be solved in time O ⋆ (2. 85 k) . Almost Forest Deletion can be solved in time O ⋆ (min { 2. 85 k · 8. 54 ℓ , 2. 7 k · 36. 61 ℓ , 3 k · 1. 78 ℓ }) . [ABSTRACT FROM AUTHOR]

Linear hyperspectral unmixing (LHU) is a class of important problems in remote sensing. It can be modelled by a linearly constrained convex optimization problem with a coupled objective function. This paper proposes an alternating direction method of multipliers (ADMM) for solving this LHU model. The special structure of the LHU model allows explicit solutions to the subproblems in the ADMM and hence the ADMM is easily implementable. The global convergence of the ADMM is established despite the existence of a coupled term in the objective function. Our numerical experiments with four data sets demonstrated that the proposed ADMM is effective for solving the LHU model. [ABSTRACT FROM AUTHOR]

The "Game of life" model was created in 1970 by the mathematician John Horton Conway using cellular automata. Since then, different extensions of these cellular automata have been used in many applications. In this work, we introduce probabilistic cellular automata which include non-deterministic rules for transitions between successive generations of the automaton together with probabilistic decisions about life and death of the cells in the next generation of the automaton. Different directions of the neighbours of each cell are treated with the possibility of applying distinct probabilities. This way, more realistic situations can be modelled and the obtained results are also non-deterministic. In this paper, we include a brief state of the art, the description of the model and some examples obtained with an implementation of the model made in Java. [ABSTRACT FROM AUTHOR]

Low-rank approximation of tensors has been widely used in high-dimensional data analysis. It usually involves singular value decomposition (SVD) of large-scale matrices with high computational complexity. Sketching is an effective data compression and dimensionality reduction technique applied to the low-rank approximation of large matrices. This paper presents two practical randomized algorithms for low-rank Tucker approximation of large tensors based on sketching and power scheme, with a rigorous error-bound analysis. Numerical experiments on synthetic and real-world tensor data demonstrate the competitive performance of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Archetypal analysis (AA) is an unsupervised learning method for exploratory data analysis. One major challenge that limits the applicability of AA in practice is the inherent computational complexity of the existing algorithms. In this paper, we provide a novel approximation approach to partially address this issue. Utilizing probabilistic ideas from high-dimensional geometry, we introduce two preprocessing techniques to reduce the dimension and representation cardinality of the data, respectively. We prove that provided data are approximately embedded in a low-dimensional linear subspace and the convex hull of the corresponding representations is well approximated by a polytope with a few vertices, our method can effectively reduce the scaling of AA. Moreover, the solution of the reduced problem is near-optimal in terms of prediction errors. Our approach can be combined with other acceleration techniques to further mitigate the intrinsic complexity of AA. We demonstrate the usefulness of our results by applying our method to summarize several moderately large-scale datasets. [ABSTRACT FROM AUTHOR]

This paper describes the methods for finding fast algorithms for computing matrix–vector products including the procedures based on the block-structured matrices. The proposed methods involve an analysis of the structural properties of matrices. The presented approaches are based on the well-known optimization techniques: the simulated annealing and the hill-climbing algorithm along with its several extensions. The main idea of the proposed methods consists in finding a decomposition of the original matrix into a sparse matrix and a matrix corresponding to an appropriate block-structured pattern. The main criterion for optimizing is a reduction of the computational cost. The methods presented in this paper can be successfully implemented in many digital signal processing tasks. [ABSTRACT FROM PUBLISHER]

In this paper we study several classes of stochastic optimization algorithms enriched with heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time momentum variants of several of these methods are studied. We choose to perform our analysis in a setting in which all of the above methods are equivalent: convex quadratic problems. We prove global non-asymptotic linear convergence rates for all methods and various measures of success, including primal function values, primal iterates, and dual function values. We also show that the primal iterates converge at an accelerated linear rate in a somewhat weaker sense. This is the first time a linear rate is shown for the stochastic heavy ball method (i.e., stochastic gradient descent method with momentum). Under somewhat weaker conditions, we establish a sublinear convergence rate for Cesàro averages of primal iterates. Moreover, we propose a novel concept, which we call stochastic momentum, aimed at decreasing the cost of performing the momentum step. We prove linear convergence of several stochastic methods with stochastic momentum, and show that in some sparse data regimes and for sufficiently small momentum parameters, these methods enjoy better overall complexity than methods with deterministic momentum. Finally, we perform extensive numerical testing on artificial and real datasets, including data coming from average consensus problems. [ABSTRACT FROM AUTHOR]

This paper is devoted to random-bit simulation of probability densities, supported on [ 0 , 1 ] {[0,1]}. The term "random-bit" means that the source of randomness for simulation is a sequence of symmetrical Bernoulli trials. In contrast to the pioneer paper [D. E. Knuth and A. C. Yao, The complexity of nonuniform random number generation, Algorithms and Complexity, Academic Press, New York 1976, 357–428], the proposed method demands the knowledge of the probability density under simulation, and not the values of the corresponding distribution function. The method is based on the so-called binary decomposition of the density and comes down to simulation of a special discrete distribution to get several principal bits of output, while further bits of output are produced by "flipping a coin". The complexity of the method is studied and several examples are presented. [ABSTRACT FROM AUTHOR]

As a special UTV decomposition, the QLP decomposition is an effective alternative of the singular value decomposition (SVD) for the low-rank approximation. In this paper, we propose a single-pass randomized QLP decomposition algorithm for computing a low-rank matrix approximation. Compared with the randomized QLP decomposition, the complexity of the proposed algorithm does not increase significantly and the data matrix needs to be accessed only once. Therefore, our algorithm is suitable for a large matrix stored outside of memory or generated by streaming data. In the error analysis, we give the matrix approximation error analysis. We also provide singular value approximation error bounds, which can track the target largest singular values of the data matrix with high probability. Numerical experiments are also reported to verify our results. [ABSTRACT FROM AUTHOR]

The low-rank approximation of a quaternion matrix has attracted growing attention in many applications including color image processing and signal processing. In this paper, based on quaternion normal distribution random sampling, we propose a randomized quaternion QLP decomposition algorithm for computing a low-rank approximation to a quaternion data matrix. For the theoretical analysis, we first present convergence results of the quaternion QLP decomposition, which provides slightly tighter upper bounds than the existing ones for the real QLP decomposition. Then, for the randomized quaternion QLP decomposition, the matrix approximation error and the singular value approximation error analyses are also established to show the proposed randomized algorithm can track the singular values of the quaternion data matrix with high probability. Finally, we present some numerical examples to illustrate the effectiveness and reliablity of the proposed algorithm. [ABSTRACT FROM AUTHOR]