Page 1

Displaying 1 – 11 of 11

Showing per page

A novel robust principal component analysis method for image and video processing

Guoqiang Huan, Ying Li, Zhanjie Song (2016)

Applications of Mathematics

The research on the robust principal component analysis has been attracting much attention recently. Generally, the model assumes sparse noise and characterizes the error term by the 1 -norm. However, the sparse noise has clustering effect in practice so using a certain p -norm simply is not appropriate for modeling. In this paper, we propose a novel method based on sparse Bayesian learning principles and Markov random fields. The method is proved to be very effective for low-rank matrix recovery...

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our...

Advice Complexity and Barely Random Algorithms

Dennis Komm, Richard Královič (2011)

RAIRO - Theoretical Informatics and Applications

Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization....

An introduction to probabilistic methods with applications

Pierre Del Moral, Nicolas G. Hadjiconstantinou (2010)

ESAIM: Mathematical Modelling and Numerical Analysis

This special volume of the ESAIM Journal, Mathematical Modelling and Numerical Analysis, contains a collection of articles on probabilistic interpretations of some classes of nonlinear integro-differential equations. The selected contributions deal with a wide range of topics in applied probability theory and stochastic analysis, with applications in a variety of scientific disciplines, including physics, biology, fluid mechanics, molecular chemistry, financial mathematics and bayesian statistics....

How the result of graph clustering methods depends on the construction of the graph

Markus Maier, Ulrike von Luxburg, Matthias Hein (2013)

ESAIM: Probability and Statistics

We study the scenario of graph-based clustering algorithms such as spectral clustering. Given a set of data points, one first has to construct a graph on the data points and then apply a graph clustering algorithm to find a suitable partition of the graph. Our main question is if and how the construction of the graph (choice of the graph, choice of parameters, choice of weights) influences the outcome of the final clustering result. To this end we study the convergence of cluster quality measures...

Robust optimality of Gaussian noise stability

Elchanan Mossel, Joe Neeman (2015)

Journal of the European Mathematical Society

We prove that under the Gaussian measure, half-spaces are uniquely the most noise stable sets. We also prove a quantitative version of uniqueness, showing that a set which is almost optimally noise stable must be close to a half-space. This extends a theorem of Borell, who proved the same result but without uniqueness, and it also answers a question of Ledoux, who asked whether it was possible to prove Borell’s theorem using a direct semigroup argument. Our quantitative uniqueness result has various...

Semidefinite Programming Based Algorithms for the Sparsest Cut Problem

Luis A.A. Meira, Flávio K. Miyazawa (2011)

RAIRO - Operations Research

In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...

Semidefinite Programming Based Algorithms for the Sparsest Cut Problem

Luis A.A. Meira, Flávio K. Miyazawa (2011)

RAIRO - Operations Research

In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...

Currently displaying 1 – 11 of 11

Page 1