This document demonstrates that the efficient approach for diagnosis of Petri nets via integer linear programming may be unable to detect a fault even if the system is diagnosable.

This paper introduces a new technique for intelligently exploring the reachability set of a spacecraft: the set of trajectories from a given initial condition that are possible under a specified range of control actions. The high dimension of this problem and the nonlinear nature of gravitational interactions make the geometry of these sets complicated, hard to compute, and all but impossible to visualize. Currently, exploration of a problem’s state space is done heuristically, based on previously identified solutions. This potentially misses out on improved mission design solutions that are not close to previous approaches. The goal of the work described here is to map out reachability sets automatically. This would not only aid human mission planners, but also allow a spacecraft to determine its own course without input from Earth-based controllers. Brute-force approaches to this are computationally prohibitive, so one must focus the effort on regions that are of interest: where neighboring trajectories diverge quickly, for instance, or come close to a body that the spacecraft is orbiting. In this paper, we focus on the first of those two criteria; the goal is to identify regions in the system’s state space where small changes have large effects— or vice versa—and concentrate the computational mesh accordingly.

We present four methods for recovering the epipolar geometry from images of smooth surfaces. In the existing methods for recovering epipolar geometry corresponding feature points are used that cannot be found in such images. The first method is based on finding corresponding characteristic points created by illumination (ICPM - illumination characteristic points' method (PM)). The second method is based on correspondent tangency points created by tangents from epipoles to outline of smooth bodies (OTPM - outline tangent PM). These two methods are exact and give correct results for real images, because positions of the corresponding illumination characteristic points and corresponding outline are known with small errors. But the second method is limited either to special type of scenes or to restricted camera motion. We also consider two more methods which are termed CCPM (curve characteristic PM) and CTPM (curve tangent PM), for searching epipolar geometry for images of smooth bodies based on a set of level curves with constant illumination intensity. The CCPM method is based on searching correspondent points on isophoto curves with the help of correlation of curvatures between these lines. The CTPM method is based on property of the tangential to isophoto curve epipolar line to map into the tangential to correspondent isophoto curves epipolar line. The standard method (SM) based on knowledge of pairs of the almost exact correspondent points. The methods have been implemented and tested by SM on pairs of real images. Unfortunately, the last two methods give us only a finite subset of solutions including "good" solution. Exception is "epipoles in infinity". The main reason is inaccuracy of assumption of constant brightness for smooth bodies. But outline and illumination characteristic points are not influenced by this inaccuracy. So, the first pair of methods gives exact results.

We consider the detection of activations over graphs under Gaussian noise, where signals are piece-wise constant over the graph. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with proveable theoretical guarantees for general graph topologies. We cast this as a hypothesis testing problem, and first provide a universal necessary condition for asymptotic distinguishability of the null and alternative hypotheses. We then introduce the spanning tree wavelet basis over graphs, a localized basis that reflects the topology of the graph, and prove that for any spanning tree, this approach can distinguish null from alternative in a low signal-to-noise regime. Lastly, we improve on this result and show that using the uniform spanning tree in the basis construction yields a randomized test with stronger theoretical guarantees that in many cases matches our necessary conditions. Specifically, we obtain near-optimal performance in edge transitive graphs, $k$-nearest neighbor graphs, and $\epsilon$-graphs.

We describe novel subgradient methods for a broad class of matrix optimization problems involving nuclear norm regularization. Unlike existing approaches, our method executes very cheap iterations by combining low-rank stochastic subgradients with efficient incremental SVD updates, made possible by highly optimized and parallelizable dense linear algebra operations on small matrices. Our practical algorithms always maintain a low-rank factorization of iterates that can be conveniently held in memory and efficiently multiplied to generate predictions in matrix completion settings. Empirical comparisons confirm that our approach is highly competitive with several recently proposed state-of-the-art solvers for such problems.

In this paper, we review the problem of matrix completion and expose its intimate relations with algebraic geometry, combinatorics and graph theory. We present the first necessary and sufficient combinatorial conditions for matrices of arbitrary rank to be identifiable from a set of matrix entries, yielding theoretical constraints and new algorithms for the problem of matrix completion. We conclude by algorithmically evaluating the tightness of the given conditions and algorithms for practically relevant matrix sizes, showing that the algebraic-combinatoric approach can lead to improvements over state-of-the-art matrix completion methods.

Four decades after their invention, quasi-Newton methods are still state of the art in unconstrained numerical optimization. Although not usually interpreted thus, these are learning algorithms that fit a local quadratic approximation to the objective function. We show that many, including the most popular, quasi-Newton methods can be interpreted as approximations of Bayesian linear regression under varying prior assumptions. This new notion elucidates some shortcomings of classical algorithms, and lights the way to a novel nonparametric quasi-Newton method, which is able to make more efficient use of available information at computational cost similar to its predecessors.

Efficiently finding the maximum a posteriori (MAP) configuration of a graphical model is an important problem which is often implemented using message passing algorithms. The optimality of such algorithms is only well established for singly-connected graphs and other limited settings. This article extends the set of graphs where MAP estimation is in P and where message passing recovers the exact solution to so-called perfect graphs. This result leverages recent progress in defining perfect graphs (the strong perfect graph theorem), linear programming relaxations of MAP estimation and recent convergent message passing schemes. The article converts graphical models into nand Markov random fields which are straightforward to relax into linear programs. Therein, integrality can be established in general by testing for graph perfection. This perfection test is performed efficiently using a polynomial time algorithm. Alternatively, known decomposition tools from perfect graph theory may be used to prove perfection for certain families of graphs. Thus, a general graph framework is provided for determining when MAP estimation in any graphical model is in P, has an integral linear programming relaxation and is exactly recoverable by message passing.

Mixed integer linear programming (MILP) is a powerful representation often used to formulate decision-making problems under uncertainty. However, it lacks a natural mechanism to reason about objects, classes of objects, and relations. First-order logic (FOL), on the other hand, excels at reasoning about classes of objects, but lacks a rich representation of uncertainty. While representing propositional logic in MILP has been extensively explored, no theory exists yet for fully combining FOL with MILP. We propose a new representation, called first-order programming or FOP, which subsumes both FOL and MILP. We establish formal methods for reasoning about first order programs, including a sound and complete lifted inference procedure for integer first order programs. Since FOP can offer exponential savings in representation and proof size compared to FOL, and since representations and proofs are never significantly longer in FOP than in FOL, we anticipate that inference in FOP will be more tractable than inference in FOL for corresponding problems.

Database theory and database practice are typically the domain of computer scientists who adopt what may be termed an algorithmic perspective on their data. This perspective is very different than the more statistical perspective adopted by statisticians, scientific computers, machine learners, and other who work on what may be broadly termed statistical data analysis. In this article, I will address fundamental aspects of this algorithmic-statistical disconnect, with an eye to bridging the gap between these two very different approaches. A concept that lies at the heart of this disconnect is that of statistical regularization, a notion that has to do with how robust is the output of an algorithm to the noise properties of the input data. Although it is nearly completely absent from computer science, which historically has taken the input data as given and modeled algorithms discretely, regularization in one form or another is central to nearly every application domain that applies algorithms to noisy data. By using several case studies, I will illustrate, both theoretically and empirically, the nonobvious fact that approximate computation, in and of itself, can implicitly lead to statistical regularization. This and other recent work suggests that, by exploiting in a more principled way the statistical properties implicit in worst-case algorithms, one can in many cases satisfy the bicriteria of having algorithms that are scalable to very large-scale databases and that also have good inferential or predictive properties.