@inbook{18352, abstract = {Feature-based analysis is becoming a very popular approach for geometric shape analysis. Following the success of this approach in image analysis, there is a growing interest in finding analogous methods in the 3D world. Maximally stable component detection is a low computation cost and high repeatability method for feature detection in images.In this study, a diffusion-geometry based framework for stable component detection is presented, which can be used for geometric feature detection in deformable shapes.The vast majority of studies of deformable 3D shapes models them as the two-dimensional boundary of the volume of the shape. Recent works have shown that a volumetric shape model is advantageous in numerous ways as it better captures the natural behavior of non-rigid deformations. We show that our framework easily adapts to this volumetric approach, and even demonstrates superior performance.A quantitative evaluation of our methods on the SHREC’10 and SHREC’11 feature detection benchmarks as well as qualitative tests on the SCAPE dataset show its potential as a source of high-quality features. Examples demonstrating the drawbacks of surface stable components and the advantage of their volumetric counterparts are also presented.}, author = {Litman, Roee and Bronstein, Alexander and Bronstein, Michael M.}, booktitle = {Innovations for Shape Analysis}, editor = {Breuß, Michael and Bruckstein, Alfred and Maragos, Petros}, isbn = {9783642341403}, issn = {1612-3786}, pages = {161 -- 189}, publisher = {Springer Nature}, title = {{Stable Semi-local Features for Non-rigid Shapes}}, doi = {10.1007/978-3-642-34141-0_8}, year = {2013}, } @inproceedings{18385, abstract = {In this paper we present a framework for real time enhancement of speech signals. Our method leverages a new process-centric approach for sparse and parsimonious models, where the representation pursuit is obtained applying a deterministic function or process rather than solving an optimization problem. We first propose a rank-regularized robust version of non-negative matrix factorization (NMF) for modeling time-frequency representations of speech signals in which the spectral frames are decomposed as sparse linear combinations of atoms of a low-rank dictionary. Then, a parametric family of pursuit processes is derived from the iteration of the proximal descent method for solving this model. We present several experiments showing successful results and the potential of the proposed framework. Incorporating discriminative learning makes the proposed method significantly outperform exact NMF algorithms, with fixed latency and at a fraction of it's computational complexity.}, author = {Sprechmann, Pablo and Bronstein, Alexander and Bronstein, Michael and Sapiro, Guillermo}, booktitle = {2013 IEEE International Conference on Acoustics, Speech and Signal Processing}, issn = {2379-190X}, location = {Vancouver, BC, Canada}, publisher = {IEEE}, title = {{Learnable low rank sparse models for speech denoising}}, doi = {10.1109/icassp.2013.6637624}, year = {2013}, } @inproceedings{18386, abstract = {A method for removing impulse noise from audio signals by fusing multiple copies of the same recording is introduced in this paper. The proposed algorithm exploits the fact that while in general multiple copies of a given recording are available, all sharing the same master, most degradations in audio signals are record-dependent. Our method first seeks for the optimal non-rigid alignment of the signals that is robust to the presence of sparse outliers with arbitrary magnitude. Unlike previous approaches, we simultaneously find the optimal alignment of the signals and impulsive degradation. This is obtained via continuous dynamic time warping computed solving an Eikonal equation. We propose to use our approach in the derivative domain, reconstructing the signal by solving an inverse problem that resembles the Poisson image editing technique. The proposed framework is here illustrated and tested in the restoration of old gramophone recordings showing promising results; however, it can be used in other applications where different copies of the signal of interest are available and the degradations are copy-dependent.}, author = {Sprechmann, Pablo and Bronstein, Alexander and Morel, Jean-Michel and Sapiro, Guillermo}, booktitle = {2013 IEEE International Conference on Acoustics, Speech and Signal Processing}, issn = {2379-190X}, location = {Vancouver, BC, Canada}, publisher = {IEEE}, title = {{Audio restoration from multiple copies}}, doi = {10.1109/icassp.2013.6637774}, year = {2013}, } @inproceedings{18395, abstract = {Dynamic Time Warping (DTW), is a simple but efficient technique for matching sequences with rigid deformation. Therefore, it is frequently used for matching shapes in general, and shapes of handwritten words in Document Image Analysis tasks. As DTW is computationally expensive, efficient algorithms for fast computation are crucial. Retrieving images from large scale datasets using DTW, suffers from the constraint of linear searching of all sample in the datasets. Fast approximation algorithms for image retrieval are mostly based on normed spaces where the triangle inequality holds, which is unfortunately not the case with the DTW metric. In this paper we present a novel approach for fast search of handwritten words within large datasets of shapes. The presented approach is based on the Boost-Map [1] algorithm, for embedding the feature space with the DTW measurement to an euclidean space and use the Local Sensitivity Hashing algorithm (LSH) to rank the k-nearest neighbors of a query image. The algorithm, first, processes and embeds objects of the large data sets to a normed space. Fast approximation of k-nearest neighbors using LSH on the embedding space, generates the top kranked samples which are examined using the real DTW distance to give final accurate results. We demonstrate our method on a database of 45; 800 images of word-parts extracted from the IFN/ENIT database [11] and images collected from 51 different writers. Our method achieves a speedup of 4 orders of magnitude over the exact method, at the cost of only a 2:2% reduction in accuracy.}, author = {Saabni, Raid and Bronstein, Alexander}, booktitle = {2012 International Conference on Frontiers in Handwriting Recognition}, isbn = {9781467322621}, location = {Bari, Italy}, publisher = {IEEE}, title = {{Fast key-word searching using 'BoostMap' based embedding}}, doi = {10.1109/icfhr.2012.204}, year = {2013}, } @article{18421, abstract = {The use of Laplacian eigenbases has been shown to be fruitful in many computer graphics applications. Today, state-of-the-art approaches to shape analysis, synthesis, and correspondence rely on these natural harmonic bases that allow using classical tools from harmonic analysis on manifolds. However, many applications involving multiple shapes are obstacled by the fact that Laplacian eigenbases computed independently on different shapes are often incompatible with each other. In this paper, we propose the construction of common approximate eigenbases for multiple shapes using approximate joint diagonalization algorithms, taking as input a set of corresponding functions (e.g. indicator functions of stable regions) on the two shapes. We illustrate the benefits of the proposed approach on tasks from shape editing, pose transfer, correspondence, and similarity.}, author = {Kovnatsky, A. and Bronstein, M. M. and Bronstein, Alexander and Glashoff, K. and Kimmel, R.}, issn = {1467-8659}, journal = {Computer Graphics Forum}, number = {2pt4}, pages = {439--448}, publisher = {Wiley}, title = {{Coupled quasi‐harmonic bases}}, doi = {10.1111/cgf.12064}, volume = {32}, year = {2013}, } @article{18422, abstract = {We present a novel sparse modeling approach to non-rigid shape matching using only the ability to detect repeatable regions. As the input to our algorithm, we are given only two sets of regions in two shapes; no descriptors are provided so the correspondence between the regions is not know, nor we know how many regions correspond in the two shapes. We show that even with such scarce information, it is possible to establish very accurate correspondence between the shapes by using methods from the field of sparse modeling, being this, the first non-trivial use of sparse models in shape correspondence. We formulate the problem of permuted sparse coding, in which we solve simultaneously for an unknown permutation ordering the regions on two shapes and for an unknown correspondence in functional representation. We also propose a robust variant capable of handling incomplete matches. Numerically, the problem is solved efficiently by alternating the solution of a linear assignment and a sparse coding problem. The proposed methods are evaluated qualitatively and quantitatively on standard benchmarks containing both synthetic and scanned objects.}, author = {Pokrass, J. and Bronstein, Alexander and Bronstein, M. M. and Sprechmann, P. and Sapiro, G.}, issn = {1467-8659}, journal = {Computer Graphics Forum}, number = {2pt4}, pages = {459--468}, publisher = {Wiley}, title = {{Sparse modeling of intrinsic correspondences}}, doi = {10.1111/cgf.12066}, volume = {32}, year = {2013}, } @article{18437, abstract = { Elg1 and Srs2 are two proteins involved in maintaining genome stability in yeast. After DNA damage, the homotrimeric clamp PCNA, which provides stability and processivity to DNA polymerases and serves as a docking platform for DNA repair enzymes, undergoes modification by the ubiquitin-like molecule SUMO. PCNA SUMOylation helps recruit Srs2 and Elg1 to the replication fork. In the absence of Elg1, both SUMOylated PCNA and Srs2 accumulate at the chromatin fraction, indicating that Elg1 is required for removing SUMOylated PCNA and Srs2 from DNA. Despite this interaction, which suggests that the two proteins work together, double mutants elg1Δ srs2Δ have severely impaired growth as haploids and exhibit synergistic sensitivity to DNA damage and a synergistic increase in gene conversion. In addition, diploid elg1Δ srs2Δ double mutants are dead, which implies that an essential function in the cell requires at least one of the two gene products for survival. To gain information about this essential function, we have carried out a high copy number suppressor screen to search for genes that, when overexpressed, suppress the synthetic lethality between elg1Δ and srs2Δ. We report the identification of 36 such genes, which are enriched for functions related to DNA- and chromatin-binding, chromatin packaging and modification, and mRNA export from the nucleus.}, author = {Gazy, Inbal and Liefshitz, Batia and Bronstein, Alexander and Parnas, Oren and Atias, Nir and Sharan, Roded and Kupiec, Martin}, issn = {2160-1836}, journal = { G3: Genes, Genomes, Genetics}, number = {5}, pages = {917--926}, publisher = {Oxford University Press}, title = {{A genetic screen for high copy number suppressors of the synthetic lethality between elg1Δ and srs2Δ in yeast}}, doi = {10.1534/g3.113.005561}, volume = {3}, year = {2013}, } @article{18440, abstract = {In this paper, we explore the use of the diffusion geometry framework for the fusion of geometric and photometric information in local and global shape descriptors. Our construction is based on the definition of a diffusion process on the shape manifold embedded into a high-dimensional space where the embedding coordinates represent the photometric information. Experimental results show that such data fusion is useful in coping with different challenges of shape analysis where pure geometric and pure photometric methods fail.}, author = {Bronstein, Alexander and Kovnatsky, Artiom and Raviv, Dan and Bronstein, Michael M. and Kimmel, Ron}, issn = {2079-7338}, journal = {Numerical Mathematics: Theory, Methods and Applications}, number = {1}, pages = {199--222}, publisher = {Global Science Press}, title = {{Geometric and photometric data fusion in non-rigid shape analysis}}, doi = {10.4208/nmtma.2013.mssvm11}, volume = {6}, year = {2013}, } @article{18441, abstract = {Partial similarity of shapes is a challenging problem arising in many important applications in computer vision, shape analysis, and graphics, e.g. when one has to deal with partial information and acquisition artifacts. The problem is especially hard when the underlying shapes are non-rigid and are given up to a deformation. Partial matching is usually approached by computing local descriptors on a pair of shapes and then establishing a point-wise non-bijective correspondence between the two, taking into account possibly different parts. In this paper, we introduce an alternative correspondence-less approach to matching fragments to an entire shape undergoing a non-rigid deformation. We use region-wise local descriptors and optimize over the integration domains on which the integral descriptors of the two parts match. The problem is regularized using the Mumford-Shah functional. We show an efficient discretization based on the Ambrosio-Tortorelli approximation generalized to triangular point clouds and meshes, and present experiments demonstrating the success of the proposed method.}, author = {Bronstein, Alexander and Pokrass, Jonathan and Bronstein, Michael M.}, issn = {2079-7338}, journal = {Numerical Mathematics: Theory, Methods and Applications}, number = {1}, pages = {223--244}, publisher = {Global Science Press}, title = {{Partial shape matching without point-wise correspondence}}, doi = {10.4208/nmtma.2013.mssvm12}, volume = {6}, year = {2013}, } @article{22053, abstract = {We consider the Gross–Pitaevskii equation on R^4 and the cubic-quintic nonlinear Schrödinger equation (NLS) on R^3 with non-vanishing boundary conditions at spatial infinity. By viewing these equations as perturbations to the energy-critical NLS, we prove that they are globally well-posed in their energy spaces. In particular, we prove unconditional uniqueness in the energy spaces for these equations.}, author = {Killip, Rowan and Oh, Tadahiro and Pocovnicu, Oana and Visan, Monica}, issn = {1945-001X}, journal = {Mathematical Research Letters}, keywords = {NLS, Gross–Pitaevskii equation, non-vanishing boundary condition}, number = {5}, pages = {969--986}, publisher = {International Press of Boston}, title = {{Global well-posedness of the Gross–Pitaevskii and cubic-quintic nonlinear Schrödinger equations with non-vanishing boundary conditions}}, doi = {10.4310/mrl.2012.v19.n5.a1}, volume = {19}, year = {2013}, } @article{2698, abstract = {We consider non-interacting particles subject to a fixed external potential V and a self-generated magnetic field B. The total energy includes the field energy β∫B2 and we minimize over all particle states and magnetic fields. In the case of spin-1/2 particles this minimization leads to the coupled Maxwell-Pauli system. The parameter β tunes the coupling strength between the field and the particles and it effectively determines the strength of the field. We investigate the stability and the semiclassical asymptotics, h→0, of the total ground state energy E(β,h,V). The relevant parameter measuring the field strength in the semiclassical limit is κ=βh. We are not able to give the exact leading order semiclassical asymptotics uniformly in κ or even for fixed κ. We do however give upper and lower bounds on E with almost matching dependence on κ. In the simultaneous limit h→0 and κ→∞ we show that the standard non-magnetic Weyl asymptotics holds. The same result also holds for the spinless case, i.e. where the Pauli operator is replaced by the Schrödinger operator.}, author = {Erdös, László and Fournais, Søren and Solovej, Jan}, journal = {Journal of the European Mathematical Society}, number = {6}, pages = {2093 -- 2113}, publisher = {EMS Press}, title = {{Stability and semiclassics in self-generated fields}}, doi = {10.4171/JEMS/416}, volume = {15}, year = {2013}, } @inproceedings{2328, abstract = {Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on identifying the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.}, author = {Henzinger, Thomas A and Sezgin, Ali and Vafeiadis, Viktor}, location = {Buenos Aires, Argentina}, pages = {242 -- 256}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Aspect-oriented linearizability proofs}}, doi = {10.1007/978-3-642-40184-8_18}, volume = {8052}, year = {2013}, } @inproceedings{2901, abstract = { We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. }, author = {Chen, Chao and Kolmogorov, Vladimir and Yan, Zhu and Metaxas, Dimitris and Lampert, Christoph}, booktitle = {Proceedings of the 16th International Conference on Artificial Intelligence and Statistics}, location = {Scottsdale, AZ, United States}, pages = {161 -- 169}, publisher = {Journal of Machine Learning Research}, title = {{Computing the M most probable modes of a graphical model}}, volume = {31}, year = {2013}, } @article{2818, abstract = {Models of neural responses to stimuli with complex spatiotemporal correlation structure often assume that neurons are selective for only a small number of linear projections of a potentially high-dimensional input. In this review, we explore recent modeling approaches where the neural response depends on the quadratic form of the input rather than on its linear projection, that is, the neuron is sensitive to the local covariance structure of the signal preceding the spike. To infer this quadratic dependence in the presence of arbitrary (e.g., naturalistic) stimulus distribution, we review several inference methods, focusing in particular on two information theory–based approaches (maximization of stimulus energy and of noise entropy) and two likelihood-based approaches (Bayesian spike-triggered covariance and extensions of generalized linear models). We analyze the formal relationship between the likelihood-based and information-based approaches to demonstrate how they lead to consistent inference. We demonstrate the practical feasibility of these procedures by using model neurons responding to a flickering variance stimulus.}, author = {Rajan, Kanaka and Marre, Olivier and Tkacik, Gasper}, journal = {Neural Computation}, number = {7}, pages = {1661 -- 1692}, publisher = {MIT Press}, title = {{Learning quadratic receptive fields from neural responses to natural stimuli}}, doi = {10.1162/NECO_a_00463}, volume = {25}, year = {2013}, } @article{2859, abstract = {Given a continuous function f:X-R on a topological space, we consider the preimages of intervals and their homology groups and show how to read the ranks of these groups from the extended persistence diagram of f. In addition, we quantify the robustness of the homology classes under perturbations of f using well groups, and we show how to read the ranks of these groups from the same extended persistence diagram. The special case X=R3 has ramifications in the fields of medical imaging and scientific visualization.}, author = {Bendich, Paul and Edelsbrunner, Herbert and Morozov, Dmitriy and Patel, Amit}, journal = {Homology, Homotopy and Applications}, number = {1}, pages = {51 -- 72}, publisher = {International Press of Boston}, title = {{Homology and robustness of level and interlevel sets}}, doi = {10.4310/HHA.2013.v15.n1.a3}, volume = {15}, year = {2013}, } @article{2280, abstract = {The problem of packing ellipsoids of different sizes and shapes into an ellipsoidal container so as to minimize a measure of overlap between ellipsoids is considered. A bilevel optimization formulation is given, together with an algorithm for the general case and a simpler algorithm for the special case in which all ellipsoids are in fact spheres. Convergence results are proved and computational experience is described and illustrated. The motivating application-chromosome organization in the human cell nucleus-is discussed briefly, and some illustrative results are presented.}, author = {Uhler, Caroline and Wright, Stephen}, journal = {SIAM Review}, number = {4}, pages = {671 -- 706}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Packing ellipsoids with overlap}}, doi = {10.1137/120872309}, volume = {55}, year = {2013}, } @article{2256, abstract = {Linked (Open) Data - bibliographic data on the Semantic Web. Report of the Working Group on Linked Data to the plenary assembly of the Austrian Library Network (translation of the title). Linked Data stands for a certain approach to publishing data on the Web. The underlying idea is to harmonise heterogeneous data sources of different origin in order to improve their accessibility and interoperability, effectively making them queryable as a big distributed database. This report summarises relevant developments in Europe as well as the Linked Data Working Group‘s strategic and technical considerations regarding the publishing of the Austrian Library Network’s (OBV’s) bibliographic datasets. It concludes with the mutual agreement that the implementation of Linked Data principles within the OBV can only be taken into consideration accompanied by a discussion about the provision of the datasets under a free license.}, author = {Danowski, Patrick and Goldfarb, Doron and Schaffner, Verena and Seidler, Wolfram}, journal = {VÖB Mitteilungen}, number = {3/4}, pages = {559 -- 587}, publisher = {Vereinigung Österreichischer Bibliothekarinnen und Bibliothekare}, title = {{Linked (Open) Data - Bibliographische Daten im Semantic Web}}, volume = {66}, year = {2013}, } @article{2284, abstract = {Background: The brood of ants and other social insects is highly susceptible to pathogens, particularly those that penetrate the soft larval and pupal cuticle. We here test whether the presence of a pupal cocoon, which occurs in some ant species but not in others, affects the sanitary brood care and fungal infection patterns after exposure to the entomopathogenic fungus Metarhizium brunneum. We use a) a comparative approach analysing four species with either naked or cocooned pupae and b) a within-species analysis of a single ant species, in which both pupal types co-exist in the same colony. Results: We found that the presence of a cocoon did not compromise fungal pathogen detection by the ants and that species with cocooned pupae increased brood grooming after pathogen exposure. All tested ant species further removed brood from their nests, which was predominantly expressed towards larvae and naked pupae treated with the live fungal pathogen. In contrast, cocooned pupae exposed to live fungus were not removed at higher rates than cocooned pupae exposed to dead fungus or a sham control. Consistent with this, exposure to the live fungus caused high numbers of infections and fungal outgrowth in larvae and naked pupae, but not in cocooned pupae. Moreover, the ants consistently removed the brood prior to fungal outgrowth, ensuring a clean brood chamber. Conclusion: Our study suggests that the pupal cocoon has a protective effect against fungal infection, causing an adaptive change in sanitary behaviours by the ants. It further demonstrates that brood removal-originally described for honeybees as "hygienic behaviour"-is a widespread sanitary behaviour in ants, which likely has important implications on disease dynamics in social insect colonies.}, author = {Tragust, Simon and Ugelvig, Line V and Chapuisat, Michel and Heinze, Jürgen and Cremer, Sylvia}, journal = {BMC Evolutionary Biology}, number = {1}, publisher = {BioMed Central}, title = {{Pupal cocoons affect sanitary brood care and limit fungal infections in ant colonies}}, doi = {10.1186/1471-2148-13-225}, volume = {13}, year = {2013}, } @inproceedings{1387, abstract = {Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are good for trees (GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures), good for games (GFG; i.e., ones whose choices depend only on the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for ω-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata.}, author = {Boker, Udi and Kuperberg, Denis and Kupferman, Orna and Skrzypczak, Michał}, location = {Riga, Latvia}, number = {PART 2}, pages = {89 -- 100}, publisher = {Springer}, title = {{Nondeterminism in the presence of a diverse or unknown future}}, doi = {10.1007/978-3-642-39212-2_11}, volume = {7966}, year = {2013}, } @inproceedings{2517, abstract = {Traditional formal methods are based on a Boolean satisfaction notion: a reactive system satisfies, or not, a given specification. We generalize formal methods to also address the quality of systems. As an adequate specification formalism we introduce the linear temporal logic LTL[F]. The satisfaction value of an LTL[F] formula is a number between 0 and 1, describing the quality of the satisfaction. The logic generalizes traditional LTL by augmenting it with a (parameterized) set F of arbitrary functions over the interval [0,1]. For example, F may contain the maximum or minimum between the satisfaction values of subformulas, their product, and their average. The classical decision problems in formal methods, such as satisfiability, model checking, and synthesis, are generalized to search and optimization problems in the quantitative setting. For example, model checking asks for the quality in which a specification is satisfied, and synthesis returns a system satisfying the specification with the highest quality. Reasoning about quality gives rise to other natural questions, like the distance between specifications. We formalize these basic questions and study them for LTL[F]. By extending the automata-theoretic approach for LTL to a setting that takes quality into an account, we are able to solve the above problems and show that reasoning about LTL[F] has roughly the same complexity as reasoning about traditional LTL.}, author = {Almagor, Shaull and Boker, Udi and Kupferman, Orna}, location = {Riga, Latvia}, number = {Part 2}, pages = {15 -- 27}, publisher = {Springer}, title = {{Formalizing and reasoning about quality}}, doi = {10.1007/978-3-642-39212-2_3}, volume = {7966}, year = {2013}, }