BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We characterize some variations of pseudoskeleton (also called CUR) decompositions for matrices and tensors over arbitrary fields. These characterizations extend previous results to arbitrary fields and to decompositions which use generalized inverses of the constituent matrices, in contrast to Moore--Penrose pseudoinverses in prior works which are specific to real or complex valued matrices, and are significantly more structured.
Robust principal component analysis (RPCA) is a widely used tool for dimension reduction. In this work, we propose a novel non-convex algorithm, coined Iterated Robust CUR (IRCUR), for solving RPCA problems, which dramatically improves the computational efficiency in comparison with the existing algorithms. IRCUR achieves this acceleration by employing CUR decomposition when updating the low rank component, which allows us to obtain an accurate low rank approximation via only three small submatrices. Consequently, IRCUR is able to process only the small submatrices and avoid expensive computing on the full matrix through the entire algorithm. Numerical experiments establish the computational advantage of IRCUR over the state-of-art algorithms on both synthetic and real-world datasets.
This tutorial review provides a guiding reference to researchers who want to have an overview of the large body of literature about graph spanners. It reviews the current literature covering various research streams about graph spanners, such as different formulations, sparsity and lightness results, computational complexity, dynamic algorithms, and applications. As an additional contribution, we offer a list of open problems on graph spanners.
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio cloglogn, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln∣T∣+1),ℓρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and ℓ is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ≈1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal's minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.
The CUR decomposition is a factorization of a low-rank matrix obtained by selecting certain column and row submatrices of it. We perform a thorough investigation of what happens to such decompositions in the presence of noise. Since CUR decompositions are non-uniquely formed, we investigate several variants and give perturbation estimates for each in terms of the magnitude of the noise matrix in a broad class of norms which includes all Schatten p--norms. The estimates given here are qualitative and illustrate how the choice of columns and rows affects the quality of the approximation, and additionally we obtain new state-of-the-art bounds for some variants of CUR approximations.
This article studies how to form CUR decompositions of low-rank matrices via primarily random sampling, though deterministic methods due to previous works are illustrated as well. The primary problem is to determine when a column submatrix of a rank k matrix also has rank k. For random column sampling schemes, there is typically a tradeoff between the number of columns needed to be chosen and the complexity of determining the sampling probabilities. We discuss several sampling methods and their complexities as well as stability of the method under perturbations of both the probabilities and the underlying matrix. As an application, we give a high probability guarantee of the exact solution of the Subspace Clustering Problem via CUR decompositions when columns are sampled according to their Euclidean lengths.
A \Riesz-basis sequence for L2[−π,π] is a strictly increasing sequence X:=(xj)j∈Z in R such that the set of functions (e−ixj(⋅))j∈Z is a Riesz basis for L2[−π,π]. Given such a sequence and a parameter 0<h≤1, we consider interpolation of functions g∈W2k(R) at the set (hxj)j∈Z via translates of the Gaussian kernel. Existence is shown of an interpolant of the form IhX(g)(x):=j∈Z∑aje−(x−hxj)2,x∈R, which is continuous and square-integrable on R, and satisfies the interpolatory condition IhX(g)(hxj)=g(hxj),j∈Z. Moreover, use of the parameter h gives approximation rates of order hk. Namely, there is a constant independent of g such that ∥IhX(g)−g∥L2(R)≤Chk∣g∣W2k(R). Interpolation using translates of certain functions other than the Gaussian, so-called regular interpolators, is also considered and shown to exhibit the same approximation rates.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.