**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Fast recovery and approximation of hidden Cauchy structure

Abstract

We derive an algorithm of optimal complexity which determines whether a given matrix is a Cauchy matrix, and which exactly recovers the Cauchy points defining a Cauchy matrix from the matrix entries. Moreover, we study how to approximate a given matrix by a Cauchy matrix with a particular focus on the recovery of Cauchy points from noisy data. We derive an approximation algorithm of optimal complexity for this task, and prove approximation bounds. Numerical examples illustrate our theoretical results. (C) 2015 Elsevier Inc. All rights reserved.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related concepts (12)

Approximation

An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word approximation is derived from Latin approximatus, from prox

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable

Related publications (2)

Loading

Loading

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices.In the first part, we consider algorithms for building low-rank approximations of a matrix from some rows or columns of the matrix itself. We prove a priori error bounds for a greedy algorithm for cross approximation and we develop a faster and more efficient variant of an existing algorithm for column subset selection. Moreover, we present a new deterministic polynomial-time algorithm that gives a cross approximation which is quasi-optimal in the Frobenius norm. The second part of the thesis is concerned with matrix functions. We develop a divide-and-conquer algorithm for computing functions of matrices that are banded, hierarchically semiseparable, or have some other off-diagonal low-rank structure. An important building block of our approach is an existing algorithm for updating the function of a matrix that undergoes a low-rank modification (update), for which we present new convergence results. The convergence analysis of our divide-and-conquer algorithm is related to polynomial or rational approximation of the function.In the third part we consider the problem of approximating the trace of a matrix which is available indirectly, through matrix-vector multiplications. We analyze a stochastic algorithm, the Hutchinson trace estimator, for which we prove tail bounds for symmetric (indefinite) matrices. Then we apply our results to the computation of the (log)determinants of symmetric positive definite matrices.

This thesis is devoted to the design and analysis of algorithms for scheduling problems. These problems are ubiquitous in the modern world. Examples include the optimization of local transportation, managing access to concurrent resources like runways at airports and efficient execution of computing tasks on server systems. Problem instances that appear in the real world often are so large and complex that it is not possible to solve them “by hand”. This rises the need for strong algorithmic approaches, which motivates our focus of study. In this work we consider two types of scheduling problems which gained in importance due to recent technological advances. The first problem comes from the avionics industry and deals with scheduling periodically recurring tasks in a parallel computer network on a plane: Each task comes with a period p and execution time c, and needs to use a processor exclusively for c time units every p time units. The scheduling problem is to assign starting offsets for the first execution of the tasks so that no collision occurs. The second problem is a scheduling problem that arises in highly parallelized processing environments with a shared common resource, e.g., modern multi-core computer architectures. In addition to classical makespan minimization problems such as scheduling on identical machines, each job has an additional resource constraint. The scheduler must ensure that at no time, the accumulated requirement of all active jobs at that time exceeds a given limit. For both types of problems we study their algorithmic complexity in a mathematical, rigorous way by designing approximation algorithms and establishing inapproximability results. We thereby give a characterization of the approximation landscape of these problems. We also consider a more practical perspective: For an engineer from the industry, a rigorous proof that an algorithm finds a solution of certain guaranteed quality for all possible kinds of problem instances is usually not that relevant. It is rather of interest to find “good enough” or even optimal solutions for particular instances that actually appear in the real world in “reasonable” time. We show that structural insights gained in the more theoretical process of designing approximation algorithms can be highly beneficial also for obtaining practical results. In particular, we develop integer programming formulations for the avionics problem based on structural properties revealed in the design of approximation algorithms. These formulations lead to strong tools that, for the first time, enable to algorithmically solve real-world instances from our industrial partner.