Search results for "Algorithm"

showing 10 items of 4887 documents

String attractors and combinatorics on words

2019

The notion of \emph{string attractor} has recently been introduced in [Prezza, 2017] and studied in [Kempa and Prezza, 2018] to provide a unifying framework for known dictionary-based compressors. A string attractor for a word $w=w[1]w[2]\cdots w[n]$ is a subset $\Gamma$ of the positions $\{1,\ldots,n\}$, such that all distinct factors of $w$ have an occurrence crossing at least one of the elements of $\Gamma$. While finding the smallest string attractor for a word is a NP-complete problem, it has been proved in [Kempa and Prezza, 2018] that dictionary compressors can be interpreted as algorithms approximating the smallest string attractor for a given word. In this paper we explore the noti…

FOS: Computer and information sciencesSettore ING-INF/05 - Sistemi Di Elaborazione Delle InformazioniSettore INF/01 - InformaticaFormal Languages and Automata Theory (cs.FL)De Brujin wordComputer Science - Formal Languages and Automata TheoryBurrows-Wheeler transformString attractorComputer Science - Data Structures and AlgorithmsThue-Morse wordLempel-Ziv encodingBurrows-Wheeler transform; De Brujin word; Lempel-Ziv encoding; Run-length encoding; String attractor; Thue-Morse wordData Structures and Algorithms (cs.DS)Run-length encoding
researchProduct

Quasi conjunction, quasi disjunction, t-norms and t-conorms: Probabilistic aspects

2013

We make a probabilistic analysis related to some inference rules which play an important role in nonmonotonic reasoning. In a coherence-based setting, we study the extensions of a probability assessment defined on $n$ conditional events to their quasi conjunction, and by exploiting duality, to their quasi disjunction. The lower and upper bounds coincide with some well known t-norms and t-conorms: minimum, product, Lukasiewicz, and Hamacher t-norms and their dual t-conorms. On this basis we obtain Quasi And and Quasi Or rules. These are rules for which any finite family of conditional events p-entails the associated quasi conjunction and quasi disjunction. We examine some cases of logical de…

FOS: Computer and information sciencesSettore MAT/06 - Probabilita' E Statistica MatematicaInformation Systems and ManagementComputer Science - Artificial Intelligencet-Norms/conormDuality (mathematics)goodman-nguyen inclusion relation; lower/upper probability bounds; t-norms/conorms; generalized loop rule; coherence; quasi conjunction/disjunctionComputer Science::Artificial IntelligenceTheoretical Computer ScienceArtificial IntelligenceFOS: MathematicsProbabilistic analysis of algorithmsNon-monotonic logicRule of inferenceLower/upper probability boundGoodman–Nguyen inclusion relationMathematicsEvent (probability theory)Settore ING-INF/05 - Sistemi Di Elaborazione Delle InformazioniDiscrete mathematicsInterpretation (logic)Probability (math.PR)Probabilistic logicCoherence (philosophical gambling strategy)Generalized Loop ruleComputer Science ApplicationsAlgebraArtificial Intelligence (cs.AI)Control and Systems EngineeringQuasi conjunction/disjunctionCoherenceMathematics - ProbabilitySoftwareInformation Sciences
researchProduct

Fast Graph Filters for Decentralized Subspace Projection

2020

A number of inference problems with sensor networks involve projecting a measured signal onto a given subspace. In existing decentralized approaches, sensors communicate with their local neighbors to obtain a sequence of iterates that asymptotically converges to the desired projection. In contrast, the present paper develops methods that produce these projections in a finite and approximately minimal number of iterations. Building upon tools from graph signal processing, the problem is cast as the design of a graph filter which, in turn, is reduced to the design of a suitable graph shift operator. Exploiting the eigenstructure of the projection and shift matrices leads to an objective whose…

FOS: Computer and information sciencesSignal processingComputer scienceMatrix normConvex relaxationRegular polygon020206 networking & telecommunications02 engineering and technologyShift operatorStatistics - ComputationGraphsymbols.namesakeMatrix (mathematics)Approximation errorKronecker deltaSignal Processing0202 electrical engineering electronic engineering information engineeringsymbolsGraph (abstract data type)Electrical and Electronic EngineeringAlgorithmComputation (stat.CO)Subspace topologyEigenvalues and eigenvectorsIEEE Transactions on Signal Processing
researchProduct

Parsimonious adaptive rejection sampling

2017

Monte Carlo (MC) methods have become very popular in signal processing during the past decades. The adaptive rejection sampling (ARS) algorithms are well-known MC technique which draw efficiently independent samples from univariate target densities. The ARS schemes yield a sequence of proposal functions that converge toward the target, so that the probability of accepting a sample approaches one. However, sampling from the proposal pdf becomes more computationally demanding each time it is updated. We propose the Parsimonious Adaptive Rejection Sampling (PARS) method, where an efficient trade-off between acceptance rate and proposal complexity is obtained. Thus, the resulting algorithm is f…

FOS: Computer and information sciencesSignal processingSequenceComputer science020208 electrical & electronic engineeringMonte Carlo methodRejection samplingUnivariateSampling (statistics)020206 networking & telecommunicationsSample (statistics)02 engineering and technologyStatistics - ComputationAdaptive filter0202 electrical engineering electronic engineering information engineeringElectrical and Electronic EngineeringAlgorithmComputation (stat.CO)Electronics Letters
researchProduct

A quantum vocal theory of sound

2020

Concepts and formalism from acoustics are often used to exemplify quantum mechanics. Conversely, quantum mechanics could be used to achieve a new perspective on acoustics, as shown by Gabor studies. Here, we focus in particular on the study of human voice, considered as a probe to investigate the world of sounds. We present a theoretical framework that is based on observables of vocal production, and on some measurement apparati that can be used both for analysis and synthesis. In analogy to the description of spin states of a particle, the quantum-mechanical formalism is used to describe the relations between the fundamental states associated with phonetic labels such as phonation, turbule…

FOS: Computer and information sciencesSound (cs.SD)Computer scienceAudio processingAnalogyAudio processing; Quantum-inspired algorithms; Sound representation01 natural sciencesComputer Science - Sound050105 experimental psychologyTheoretical Computer Sciencesymbols.namesakeAudio and Speech Processing (eess.AS)0103 physical sciencesFOS: Electrical engineering electronic engineering information engineering0501 psychology and cognitive sciencesPhonationElectrical and Electronic Engineering010306 general physicsQuantumHuman voiceQuantum computerSound representationSettore INF/01 - Informatica05 social sciencesStatistical and Nonlinear PhysicsObservableSettore MAT/04 - Matematiche ComplementariElectronic Optical and Magnetic MaterialsVibrationClassical mechanicsFourier transformComputer Science::SoundModeling and SimulationSignal ProcessingsymbolsQuantum-inspired algorithms Audio processing Sound representationQuantum-inspired algorithmsSettore ING-INF/05 - Sistemi di Elaborazione delle InformazioniElectrical Engineering and Systems Science - Audio and Speech Processing
researchProduct

Time Difference of Arrival Estimation from Frequency-Sliding Generalized Cross-Correlations Using Convolutional Neural Networks

2020

The interest in deep learning methods for solving traditional signal processing tasks has been steadily growing in the last years. Time delay estimation (TDE) in adverse scenarios is a challenging problem, where classical approaches based on generalized cross-correlations (GCCs) have been widely used for decades. Recently, the frequency-sliding GCC (FS-GCC) was proposed as a novel technique for TDE based on a sub-band analysis of the cross-power spectrum phase, providing a structured two-dimensional representation of the time delay information contained across different frequency bands. Inspired by deep-learning-based image denoising solutions, we propose in this paper the use of convolutio…

FOS: Computer and information sciencesSound (cs.SD)Computer sciencePhase (waves)Distributed microphones02 engineering and technologyConvolutional neural networkComputer Science - Sound030507 speech-language pathology & audiology03 medical and health sciencesAudio and Speech Processing (eess.AS)FOS: Electrical engineering electronic engineering information engineering0202 electrical engineering electronic engineering information engineeringGCCRepresentation (mathematics)Signal processingbusiness.industryI.5.4Deep learningConvolutional Neural Networks020206 networking & telecommunicationsTime delay estimationMultilaterationI.2.094A12 68T10LocalizationArtificial intelligence0305 other medical sciencebusinessAlgorithmElectrical Engineering and Systems Science - Audio and Speech ProcessingI.2.0; I.5.4ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)
researchProduct

Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform

2012

Motivation The Burrows-Wheeler transform (BWT) is the foundation of many algorithms for compression and indexing of text data, but the cost of computing the BWT of very large string collections has prevented these techniques from being widely applied to the large sets of sequences often encountered as the outcome of DNA sequencing experiments. In previous work, we presented a novel algorithm that allows the BWT of human genome scale data to be computed on very moderate hardware, thus enabling us to investigate the BWT as a tool for the compression of such datasets. Results We first used simulated reads to explore the relationship between the level of compression and the error rate, the leng…

FOS: Computer and information sciencesStatistics and ProbabilityBurrows–Wheeler transformComputer scienceData_CODINGANDINFORMATIONTHEORYBurrows-Wheeler transformcomputer.software_genreBiochemistryBurrows-Wheeler transform; Data Compression; Next-generation sequencingComputer Science - Data Structures and AlgorithmsEscherichia coliCode (cryptography)HumansOverhead (computing)Data Structures and Algorithms (cs.DS)Computer SimulationQuantitative Biology - GenomicsMolecular BiologyGenomics (q-bio.GN)Genome HumanString (computer science)Search engine indexingSortingGenomicsSequence Analysis DNAConstruct (python library)Data CompressionComputer Science ApplicationsComputational MathematicsComputational Theory and MathematicsFOS: Biological sciencesNext-generation sequencingData miningDatabases Nucleic AcidcomputerAlgorithmsData compression
researchProduct

Causal Effect Identification from Multiple Incomplete Data Sources: A General Search-Based Approach

2021

Causal effect identification considers whether an interventional probability distribution can be uniquely determined without parametric assumptions from measured source distributions and structural knowledge on the generating system. While complete graphical criteria and procedures exist for many identification problems, there are still challenging but important extensions that have not been considered in the literature. To tackle these new settings, we present a search algorithm directly over the rules of do-calculus. Due to generality of do-calculus, the search is capable of taking more advanced data-generating mechanisms into account along with an arbitrary type of both observational and…

FOS: Computer and information sciencesStatistics and ProbabilityComputer Science - Machine LearningcausalityComputer Science - Artificial IntelligenceHeuristic (computer science)Computer scienceeducationMachine Learning (stat.ML)transportabilitycomputer.software_genre01 natural sciencesMachine Learning (cs.LG)R-kielimissing dataQA76.75-76.765; QA273-280010104 statistics & probabilitydo-calculuscausality; do-calculus; selection bias; transportability; missing data; case-control design; meta-analysisStatistics - Machine LearningSearch algorithmselection bias0101 mathematicsParametric statisticspäättelymeta-analyysicase-control designhakualgoritmit113 Computer and information sciencesMissing datameta-analysisIdentification (information)Artificial Intelligence (cs.AI)Causal inferencekausaliteettiIdentifiabilityProbability distributionData miningStatistics Probability and UncertaintycomputerSoftwareJournal of Statistical Software
researchProduct

Unbiased Inference for Discretely Observed Hidden Markov Model Diffusions

2021

We develop a Bayesian inference method for diffusions observed discretely and with noise, which is free of discretisation bias. Unlike existing unbiased inference methods, our method does not rely on exact simulation techniques. Instead, our method uses standard time-discretised approximations of diffusions, such as the Euler--Maruyama scheme. Our approach is based on particle marginal Metropolis--Hastings, a particle filter, randomised multilevel Monte Carlo, and importance sampling type correction of approximate Markov chain Monte Carlo. The resulting estimator leads to inference without a bias from the time-discretisation as the number of Markov chain iterations increases. We give conver…

FOS: Computer and information sciencesStatistics and ProbabilityDiscretizationComputer scienceMarkovin ketjutInference010103 numerical & computational mathematicssequential Monte CarloBayesian inferenceStatistics - Computation01 natural sciencesMethodology (stat.ME)010104 statistics & probabilitysymbols.namesakediffuusio (fysikaaliset ilmiöt)FOS: MathematicsDiscrete Mathematics and Combinatorics0101 mathematicsHidden Markov modelComputation (stat.CO)Statistics - Methodologymatematiikkabayesilainen menetelmäApplied MathematicsProbability (math.PR)diffusionmatemaattiset menetelmätMarkov chain Monte CarloMarkov chain Monte CarloMonte Carlo -menetelmätNoiseimportance sampling65C05 (primary) 60H35 65C35 65C40 (secondary)Modeling and Simulationsymbolsmatemaattiset mallitStatistics Probability and Uncertaintymultilevel Monte CarloParticle filterAlgorithmMathematics - ProbabilityImportance samplingSIAM/ASA Journal on Uncertainty Quantification
researchProduct

Grapham: Graphical models with adaptive random walk Metropolis algorithms

2008

Recently developed adaptive Markov chain Monte Carlo (MCMC) methods have been applied successfully to many problems in Bayesian statistics. Grapham is a new open source implementation covering several such methods, with emphasis on graphical models for directed acyclic graphs. The implemented algorithms include the seminal Adaptive Metropolis algorithm adjusting the proposal covariance according to the history of the chain and a Metropolis algorithm adjusting the proposal scale based on the observed acceptance probability. Different variants of the algorithms allow one, for example, to use these two algorithms together, employ delayed rejection and adjust several parameters of the algorithm…

FOS: Computer and information sciencesStatistics and ProbabilityMarkov chainAdaptive algorithmApplied MathematicsRejection samplingMarkov chain Monte CarloMultiple-try MetropolisStatistics - ComputationStatistics::ComputationComputational Mathematicssymbols.namesakeMetropolis–Hastings algorithmComputational Theory and MathematicssymbolsGraphical modelAlgorithmComputation (stat.CO)MathematicsGibbs samplingComputational Statistics & Data Analysis
researchProduct