We propose a generic variance-reduced algorithm, which we call MUltiple randomized algorithm (MURANA), for minimizing a sum of several smooth functions plus a regularizer, in a sequential or distributed manner. Our me...
详细信息
We propose a generic variance-reduced algorithm, which we call MUltiple randomized algorithm (MURANA), for minimizing a sum of several smooth functions plus a regularizer, in a sequential or distributed manner. Our method is formulated with general stochastic operators, which allow us to model various strategies for reducing the computational complexity. For example, MURANA supports sparse activation of the gradients, and also reduction of the communication load via compression of the update vectors. This versatility allows MURANA to cover many existing randomization mechanisms within a unified framework, which also makes it possible to design new methods as special cases.
We propose two random low-rank approximation algorithms based on sparse projection, SEMHMT and SEMTropp. Compared with HMT and Tropp algorithms, we mainly introduce Sparse Embedding Matrix (SEM) as sparse projection t...
详细信息
Tensor recovery has recently arisen in a lot of application fields, such as transportation, medical imaging, and remote sensing. Under the assumption that signals possess sparse and/or low-rank structures, many tensor...
详细信息
Tensor recovery has recently arisen in a lot of application fields, such as transportation, medical imaging, and remote sensing. Under the assumption that signals possess sparse and/or low-rank structures, many tensor recovery methods have been developed to apply various regularization techniques together with the operator-splitting type of algorithms. Due to the unprecedented growth of data, it becomes increasingly desirable to use streamlined algorithms to achieve real-time computation, such as stochastic optimization algorithms that have recently emerged as an efficient family of methods in machine learning. In this work, we propose a novel algorithmic framework based on the Kaczmarz algorithm for tensor recovery. We provide thorough convergence analysis and its applications from the vector case to the tensor one. Numerical results on a variety of tensor recovery applications, including sparse signal recovery, low-rank tensor recovery, image inpainting, and deconvolution, illustrate the enormous potential of the proposed methods.
In this paper we consider the existence of Hamilton cycles and perfect matchings in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic pl...
详细信息
In this paper we consider the existence of Hamilton cycles and perfect matchings in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, "short distances" and a non-vanishing clustering coefficient. The model is specified using three parameters: the number of nodes n, which we think of as going to infinity, and alpha, nu > 0, which we think of as constant. Roughly speaking alpha controls the power law exponent of the degree sequence and nu the average degree. Here we show that for every alpha < 1/2 and nu = nu(alpha) sufficiently small, the model does not contain a perfect matching with high probability, whereas for every alpha < 1/2 and nu = nu(alpha) sufficiently large, the model contains a Hamilton cycle with high probability. (C) 2020 Elsevier B.Y. All rights reserved.
Consider a totally ordered set S of n elements;as an example, a set of tennis players and their rankings. Further assume that their ranking is a total order and thus satisfies transitivity and anti-symmetry. Following...
详细信息
Consider a totally ordered set S of n elements;as an example, a set of tennis players and their rankings. Further assume that their ranking is a total order and thus satisfies transitivity and anti-symmetry. Following Frances Yao (1974), an element (player) is said to be (i, j)-mediocre if it is neither among the top i nor among the bottom j elements of S. Finding a mediocre element is closely related to finding the median element. More than 40 years ago, Yao suggested a very simple and elegant algorithm for finding an (i, j)-mediocre element: Pick i+j+1 elements arbitrarily and select the (i+1)-th largest among them. She also asked: "Is this the best algorithm?" No one seems to have found a better algorithm ever since. We first provide a deterministic algorithm that beats the worst-case comparison bound in Yao's algorithm for a large range of values of i (and corresponding suitable j = j(i)) even if the current best selection algorithm is used. We then repeat the exercise for randomized algorithms;the average number of comparisons of our algorithm beats the average comparison bound in Yao's algorithm for another large range of values of i (and corresponding suitable j = j(i)) even if the best selection algorithm is used;the improvement is most notable in the symmetric case i = j. Moreover, the tight bound obtained in the analysis of Yao's algorithm allows us to give a definite answer for this class of algorithms. In summary, we answer Yao's question as follows: (i) "Presently not" for deterministic algorithms and (ii) "Definitely not" for randomized algorithms. (In fairness, it should be said however that Yao posed the question in the context of deterministic algorithms.) (C) 2021 Elsevier B.V. All rights reserved.
We present the randomized QLP (RQLP) algorithm and its enhanced version (ERQLP) for computing a low-rank approximation to a matrix A of size m x n such that A approximate to QLP(T) , where L is a rank-k lower-triangul...
详细信息
We present the randomized QLP (RQLP) algorithm and its enhanced version (ERQLP) for computing a low-rank approximation to a matrix A of size m x n such that A approximate to QLP(T) , where L is a rank-k lower-triangular matrix, Q and P are column orthogonal matrices. The implementation of RQLP and ERQLP needs O(mnk) flops, which are mainly applied in BLAS-3 operations. We derive the lower bounds on the L-values, which can track the singular values of A approximately. Our claims are supported by numerical experiments. (C) 2020 Elsevier Inc. All rights reserved.
Let G be a directed graph with an integral cost on each edge. For a given positive integer k, the k-length negative cost cycle (kLNCC) problem is to determine whether G contains a negative cost cycle with at least k e...
详细信息
Let G be a directed graph with an integral cost on each edge. For a given positive integer k, the k-length negative cost cycle (kLNCC) problem is to determine whether G contains a negative cost cycle with at least k edges. Because of its applications in deadlock avoidance in synchronized streaming computing network, kLNCC was first studied in paper (Li et al. in Proceedings of the 22nd ACM symposium on parallelism in algorithms and architectures, pp 243-252, 2010), but remains open whether the problem is NP-hard. In this paper, we first show that an even harder problem, the fixed-point k-length negative cost cycle trail (FPkLNCCT) problem that is to determine whether G contains a negative closed trail enrouting a given vertex (as the fixed point) and containing only cycles with at least k edges, is NP-complete in a multigraph even when k = 3 by reducing from the 3SAT problem. Then, we prove the NP-completeness of kLNCC by giving amore sophisticated reduction from the 3 occurrence 3-satisfiability (3O3SAT) problem which is knownNP-complete. The complexity result for kLNCC is interesting since polynomial-time algorithms are known for both 2LNCC, which is actually equivalent to negative cycle detection, and the k-cycle problem, which is to determine whether G contains a cycle with of length at least k. Thus, this paper closes the open problem proposed by Li et al. (2010) whether kLNCC admits polynomial-time algorithms. Last but not the least, we present for 3LNCC a randomized algorithm that, if G contains a negative cycle of length at most L, can find a solution with a probability 1- is an element of for any is an element of. (0, 1] within runtime O(2min{L, h} mn is an element of ln 1 is an element of is an element of), where m, n and h are respectively the numbers of edges, vertices and length 2 negative cost cycles in G.
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 nu...
详细信息
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.
作者：
Liu, RuijieLi, LinlinYang, YingPeking Univ
Coll Engn Dept Mech & Engn Sci State Key Lab Turbulence & Complex Syst Beijing 100871 Peoples R China Univ Sci & Technol Beijing
Sch Automat & Elect Engn Minist Educ Key Lab Knowledge Automat Ind Proc Beijing 100083 Peoples R China
This brief is devoted to the issues of performance supervised fault detection (FD) for two types of feedback control systems by adopting the novel performance residual as the process evaluator. Specifically, for a cla...
详细信息
This brief is devoted to the issues of performance supervised fault detection (FD) for two types of feedback control systems by adopting the novel performance residual as the process evaluator. Specifically, for a class of uncertain state feedback control systems, the boundaries of the performance residual caused by the model uncertainties are analyzed theoretically, then the randomized algorithm is exploited to construct the threshold, aiming at avoiding the worst-case handling and improving the FD performance. The second part considers the general dynamic output feedback control systems with external reference signals. For the FD purpose, the performance residual is derived based on the backward computation, and the state variables of the closed-loop system are constructed by the accessible input, output, and reference signals to release the strict requirements for full state measurements. Finally, the effectiveness of the developed FD approaches is demonstrated on the model of a DC motor system.
An accelerated least-squares approach is introduced in this work by incorporating a greedy point selection method with randomized singular value decomposition (rSVD) to reduce the computational complexity of missing d...
详细信息
An accelerated least-squares approach is introduced in this work by incorporating a greedy point selection method with randomized singular value decomposition (rSVD) to reduce the computational complexity of missing data reconstruction. The rSVD is used to speed up the computation of a low-dimensional basis that is required for the least-squares projection by employing randomness to generate a small matrix instead of a large matrix from high-dimensional data. A greedy point selection algorithm, based on the discrete empirical interpolation method, is then used to speed up the reconstruction process in the least-squares approximation. The accuracy and computational time reduction of the proposed method are demonstrated through three numerical experiments. The first two experiments consider standard testing images with missing pixels uniformly distributed on them, and the last numerical experiment considers a sequence of many incomplete two-dimensional miscible flow images. The proposed method is shown to accelerate the reconstruction process while maintaining roughly the same order of accuracy when compared to the standard least-squares approach.
暂无评论