Computing eigenvalue bounds for iterative subspace matrix methods

A procedure is presented for the computation of bounds to eigenvalues of the generalized hermitian eigenvalue problem and to the standard hermitian eigenvalue problem. This procedure is applicable to iterative subspace eigenvalue methods and to both outer and inner eigenvalues. The Ritz values and their corresponding residual norms, all of which are computable quantities, are needed by the procedure. Knowledge of the exact eigenvalues is not needed by the procedure, but it must be known that the computed Ritz values are isolated from exact eigenvalues outside of the Ritz spectrum and that there are no skipped eigenvalues within the Ritz spectrum range. A multipass refinement procedure is described to compute the bounds for each Ritz value. This procedure requires O(m) effort where m is the subspace dimension for each pass.     

Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs

We present two efficient algorithms for the minimum-cost flow problem in which arc costs are piecewise-linear and convex. Our algorithms are based on novel algorithms of Orlin, which were developed for the case of linear arc costs. Our first algorithm uses the Edmonds-Karp scaling technique. Its complexity isO(M logU(m+n logM)) for a network withn vertices,m arcs, M linear cost segments, and an upper boundU on the supplies and the capacities. The second algorithm is a strongly polynomial version of the first, and it uses Tardos's idea of contraction. Its complexity isO(M logM(m+n logM)). Both algorithms improve by a factor of at leastM/m the complexity of directly applying existing algorithms to a transformed network in which arc costs are linear.The final stage of this work was performed while Ron Shamir was a visitor at DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), Rutgers University. Supported in part by National Science Foundation Grant NSF-STC88-09648, and by Air Force Grants AFOSR-89-0512 and AFOSR-90-0008.     

Algorithmic stability and sanity-check bounds for leave-one-out cross-validation.

In this article we prove sanity-check bounds for the error of the leave-one-out cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate is not much worse than that of the training error estimate. The name sanity check refers to the fact that although we often expect the leave-one-out estimate to perform considerably better than the training error estimate, we are here only seeking assurance that its performance will not be considerably worse. Perhaps surprisingly, such assurance has been given only for limited cases in the prior literature on cross-validation. Any nontrivial bound on the error of leave-one-out must rely on some notion of algorithmic stability. Previous bounds relied on the rather strong notion of hypothesis stability, whose application was primarily limited to nearest-neighbor and other local algorithms. Here we introduce the new and weaker notion of error stability and apply it to obtain sanity-check bounds for leave-one-out for other classes of learning algorithms, including training error minimization procedures and Bayesian algorithms. We also provide lower bounds demonstrating the necessity of some form of error stability for proving bounds on the error of the leave-one-out estimate, and the fact that for training error minimization algorithms, in the worst case such bounds must still depend on the Vapnik-Chervonenkis dimension of the hypothesis class.     

Robust fault detection using Luenberger-type unknown input observers-a parametric approach

A new parametric observer-based approach for robust fault detection in multivariable linear systems with unknown disturbances is proposed. The residual is generated through utilizing a Luenberger function observer. By using a parametric solution to a class of generalized Sylvester matrix equations, a parametrization is proposed for the residual generator on the basis of a Luenberger function observer. By further properly constraining the design parameters provided in the Luenberger observer design, the effect of the unknown disturbance is decoupled from the residual signal. The proposed approach provides all the degrees of freedom and is demonstrated to be simple and effective.     

Common Knowledge and Update in Finite Environments

Logics of knowledge have been shown to provide a useful approach to the high level specification and analysis of distributed systems. It has been proposed that such systems can be developed using knowledge- based protocols, in which agents' actions have preconditions that test their state of knowledge. Both computer-assisted analysis of the knowledge properties of systems and automated compilation of knowledge-based protocols require the development of algorithms for the computation of states of knowledge. This paper studies one of the computational problems of interest, the model checking problem for knowledge formulae in the S5_nKripke structures generated by finite state environments in which states determine an observation for each agent. Agents are assumed to have perfect recall and may operate synchronously or asynchronously. It is shown that, in this setting, model checking of common knowledge formulae is intractable, but efficient incremental algorithms are developed for formulae containing only knowledge operators. Connections to knowledge updates and compilation of knowledge-based protocols are discussed.     

利用电场感应器件MC33794测定液体高度

电场成像器件IC(MC33794)如今,设计工程师在需要非接触探测和三维(3D)电场成像的嵌入式系统中使用MC33794,可减少系统所需器件和成本。这款IC支持微控制器及多达9个简单的电极。这些电极均可独立使用,以提供在微弱电场中的物体尺寸和位置等信息。下文描述了利用此技术如何无干扰地测定液体高度。水的检测电场成像技术非常适合于非导电容器内液体高度的测定。测定工作可以在容器外完成,而且测量时无需内部或接地结构。这种方法可以测量任何介电常数的导电液体,或者介电常数比一般值大很多的非导电液体。水的测定可以通过放置于容器外的电…     

Topology-Invariant Similarity of Nonrigid Shapes

This paper explores the problem of similarity criteria between nonrigid shapes. Broadly speaking, such criteria are divided into intrinsic and extrinsic, the first referring to the metric structure of the object and the latter to how it is laid out in the Euclidean space. Both criteria have their advantages and disadvantages: extrinsic similarity is sensitive to nonrigid deformations, while intrinsic similarity is sensitive to topological noise. In this paper, we approach the problem from the perspective of metric geometry. We show that by unifying the extrinsic and intrinsic similarity criteria, it is possible to obtain a stronger topology-invariant similarity, suitable for comparing deformed shapes with different topology. We construct this new joint criterion as a tradeoff between the extrinsic and intrinsic similarity and use it as a set-valued distance. Numerical results demonstrate the efficiency of our approach in cases where using either extrinsic or intrinsic criteria alone would fail.     

Sublinear Algorithms for Approximating String Compressibility

We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and a variant of Lempel-Ziv (LZ77), and present sublinear algorithms for approximating compressibility with respect to both schemes. We also give several lower bounds that show that our algorithms for both schemes cannot be improved significantly. Our investigation of LZ77 yields results whose interest goes beyond the initial questions we set out to study. In particular, we prove combinatorial structural lemmas that relate the compressibility of a string with respect to LZ77 to the number of distinct short substrings contained in it (its ?th subword complexity , for small ?). In addition, we show that approximating the compressibility with respect to LZ77 is related to approximating the support size of a distribution.     

TRADE‐OFF BETWEEN APPROXIMATION ACCURACY AND COMPLEXITY FOR TS FUZZY MODELS

This paper proposes a transformation method that serves the trade‐off between the modelling complexity and accuracy of multi‐variable Takagi‐Sugeno fuzzy inference operator‐based modelling (TS fuzzy modelling). The relation between the number of fuzzy rules and the modelling accuracy is defined in the paper. The proposed transformation method is capable of finding the minimal number of fuzzy rules for a given accuracy of a given TS fuzzy model. A case study, focusing on a benchmark problem of fault diagnosis, developed in the framework of EC‐founded Research Training Network DAMADICS, of an actuator in a sugar factory, is presented to provide feasibility of the proposed method.     

Illustrative White Matter Fiber Bundles

Diffusion Tensor Imaging (DTI) has made feasible the visualization of the fibrous structure of the brain white matter. In the last decades, several fiber‐tracking methods have been developed to reconstruct the fiber tracts from DTI data. Usually these fiber tracts are shown individually based on some selection criteria like region of interest. However, if the white matter as a whole is being visualized clutter is generated by directly rendering the individual fiber tracts. Often users are actually interested in fiber bundles, anatomically meaningful entities that abstract from the fibers they contain. Several clustering techniques have been developed that try to group the fiber tracts in fiber bundles. However, even if clustering succeeds, the complex nature of white matter still makes it difficult to investigate. In this paper, we propose the use of illustration techniques to ease the exploration of white matter clusters. We create a technique to visualize an individual cluster as a whole. The amount of fibers visualized for the cluster is reduced to just a few hint lines, and silhouette and contours are used to improve the definition of the cluster borders. Multiple clusters can be easily visualized by a combination of the single cluster visualizations. Focus+context concepts are used to extend the multiple‐cluster renderings. Exploded views ease the exploration of the focus cluster while keeping the context clusters in an abstract form. Real‐time results are achieved by the GPU implementation of the presented techniques.