Search results for "algorithm"

showing 10 items of 4887 documents

Panel Data Analysis via Mechanistic Models

2018

Panel data, also known as longitudinal data, consist of a collection of time series. Each time series, which could itself be multivariate, comprises a sequence of measurements taken on a distinct unit. Mechanistic modeling involves writing down scientifically motivated equations describing the collection of dynamic systems giving rise to the observations on each unit. A defining characteristic of panel systems is that the dynamic interaction between units should be negligible. Panel models therefore consist of a collection of independent stochastic processes, generally linked through shared parameters while also having unit-specific parameters. To give the scientist flexibility in model spe…

FOS: Computer and information sciencesStatistics and ProbabilityMultivariate statisticsSeries (mathematics)Longitudinal dataComputer science05 social sciences01 natural sciencesMethodology (stat.ME)010104 statistics & probabilityNonlinear system0502 economics and business0101 mathematicsStatistics Probability and UncertaintyParticle filterAlgorithmStatistics - Methodology050205 econometrics Panel dataSequence (medicine)Journal of the American Statistical Association
researchProduct

Binary jumbled string matching for highly run-length compressible texts

2012

The Binary Jumbled String Matching problem is defined as: Given a string $s$ over $\{a,b\}$ of length $n$ and a query $(x,y)$, with $x,y$ non-negative integers, decide whether $s$ has a substring $t$ with exactly $x$ $a$'s and $y$ $b$'s. Previous solutions created an index of size O(n) in a pre-processing step, which was then used to answer queries in constant time. The fastest algorithms for construction of this index have running time $O(n^2/\log n)$ [Burcsi et al., FUN 2010; Moosa and Rahman, IPL 2010], or $O(n^2/\log^2 n)$ in the word-RAM model [Moosa and Rahman, JDA 2012]. We propose an index constructed directly from the run-length encoding of $s$. The construction time of our index i…

FOS: Computer and information sciencesString algorithmsStructure (category theory)Binary numberG.2.1Data_CODINGANDINFORMATIONTHEORY0102 computer and information sciences02 engineering and technologyString searching algorithm01 natural sciencesComputer Science - Information RetrievalTheoretical Computer ScienceCombinatoricsdata structuresSimple (abstract algebra)Computer Science - Data Structures and AlgorithmsString algorithms; jumbled pattern matching; prefix normal form; data structures0202 electrical engineering electronic engineering information engineeringParikh vectorData Structures and Algorithms (cs.DS)Run-length encodingMathematics68W32 68P05 68P20String (computer science)prefix normal formSubstringComputer Science Applicationsjumbled pattern matching010201 computation theory & mathematicsData structureSignal ProcessingRun-length encoding020201 artificial intelligence & image processingConstant (mathematics)Information Retrieval (cs.IR)Information SystemsInformation Processing Letters
researchProduct

Forrelation

2014

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(√(N)log(N)) queries (improving an Ω(N[superscript 1/4]) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N[superscript 1-1/2t])-query randomized algorithm. Thus, resolving an open questi…

FOS: Computer and information sciencesTheoretical computer scienceGeneral Computer ScienceComputational complexity theoryComputer scienceGeneralizationGeneral MathematicsSeparation (aeronautics)FOS: Physical sciences0102 computer and information sciencesComputational Complexity (cs.CC)01 natural sciencesUpper and lower boundsCombinatorics0103 physical sciences010306 general physicsBoolean functionQuantumComputer Science::DatabasesQuantum computerMathematicsDiscrete mathematicsQuantum PhysicsFunction (mathematics)Randomized algorithmComputer Science - Computational Complexity010201 computation theory & mathematicsQuantum algorithmQuantum Physics (quant-ph)Proceedings of the forty-seventh annual ACM symposium on Theory of Computing
researchProduct

Knowledge Base Approach for 3D Objects Detection in Point Clouds Using 3D Processing and Specialists Knowledge

2012

This paper presents a knowledge-based detection of objects approach using the OWL ontology language, the Semantic Web Rule Language, and 3D processing built-ins aiming at combining geometrical analysis of 3D point clouds and specialist's knowledge. Here, we share our experience regarding the creation of 3D semantic facility model out of unorganized 3D point clouds. Thus, a knowledge-based detection approach of objects using the OWL ontology language is presented. This knowledge is used to define SWRL detection rules. In addition, the combination of 3D processing built-ins and topological Built-Ins in SWRL rules allows a more flexible and intelligent detection, and the annotation of objects …

FOS: Computer and information sciencesTopologic analysisComputer Science - Artificial IntelligenceSemantic facility information modelGeometric analysis[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]Artificial Intelligence (cs.AI)3D processing algorithmSemantic VRML modelknowledge modelingontology3D scene reconstructionobject identification[ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI]Semantic web
researchProduct

Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness

2016

We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.

FOS: Computer and information sciencesVertex (graph theory)Quantum PhysicsNuclear and High Energy PhysicsReduction (recursion theory)Two-graphFOS: Physical sciencesGeneral Physics and AstronomyStatistical and Nonlinear PhysicsTheoretical Computer ScienceCombinatoricsComputational Theory and MathematicsComputer Science - Data Structures and AlgorithmsBipartite graphGraph (abstract data type)Adjacency listData Structures and Algorithms (cs.DS)Quantum algorithmAdjacency matrixQuantum Physics (quant-ph)Mathematical PhysicsMathematicsofComputing_DISCRETEMATHEMATICSMathematicsQuantum Information and Computation
researchProduct

Statistical Performance Analysis of a Fast Super-Resolution Technique Using Noisy Translations.

2014

It is well known that the registration process is a key step for super-resolution reconstruction. In this work, we propose to use a piezoelectric system that is easily adaptable on all microscopes and telescopes for controlling accurately their motion (down to nanometers) and therefore acquiring multiple images of the same scene at different controlled positions. Then a fast super-resolution algorithm \cite{eh01} can be used for efficient super-resolution reconstruction. In this case, the optimal use of $r^2$ images for a resolution enhancement factor $r$ is generally not enough to obtain satisfying results due to the random inaccuracy of the positioning system. Thus we propose to take seve…

FOS: Computer and information sciences[ INFO.INFO-TS ] Computer Science [cs]/Signal and Image ProcessingPositioning systemComputer scienceComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISIONsuper-resolution02 engineering and technologyIterative reconstructionMethodology (stat.ME)[INFO.INFO-TS]Computer Science [cs]/Signal and Image ProcessingPosition (vector)[ INFO.INFO-TI ] Computer Science [cs]/Image Processing0202 electrical engineering electronic engineering information engineeringComputer visionImage resolutionStatistics - Methodologyerror analysis[STAT.AP]Statistics [stat]/Applications [stat.AP]business.industryreconstruction algorithms[ STAT.AP ] Statistics [stat]/Applications [stat.AP]Process (computing)high-resolution imaging020206 networking & telecommunicationsFunction (mathematics)Computer Graphics and Computer-Aided DesignSuperresolutionperformance evaluation[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV]microscopy020201 artificial intelligence & image processingAlgorithm designArtificial intelligencebusinessSoftwareIEEE transactions on image processing : a publication of the IEEE Signal Processing Society
researchProduct

Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees

2017

International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…

FOS: Computer and information sciences[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]Discrete Mathematics (cs.DM)Spanning trees[ INFO.INFO-NI ] Computer Science [cs]/Networking and Internet Architecture [cs.NI]0102 computer and information sciences02 engineering and technologyMinimum spanning tree[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]01 natural sciencesConnected dominating setCombinatorics[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI]0202 electrical engineering electronic engineering information engineeringDiscrete Mathematics and CombinatoricsGridMathematicsMinimum degree spanning treeDiscrete mathematics020203 distributed computingTrémaux treeSpanning treeApplied MathematicsShortest-path treeWeight-balanced tree[ INFO.INFO-DM ] Computer Science [cs]/Discrete Mathematics [cs.DM]Disjoint connected dominating setsIndependent spanning trees[ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]010201 computation theory & mathematicsReverse-delete algorithmCompletely independent spanning treesComputer Science - Discrete MathematicsMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

Determinantal sets, singularities and application to optimal control in medical imagery

2016

International audience; Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures. Geometric optimal control leads us here to analyze mero-morphic vector fields depending upon physical parameters , and having their singularities defined by a deter-minantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in som…

FOS: Computer and information sciences[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]Computer Science - Symbolic Computation0209 industrial biotechnologyPolynomialRank (linear algebra)010102 general mathematicsBoundary (topology)Field (mathematics)02 engineering and technologySymbolic Computation (cs.SC)Optimal control01 natural sciencesPolynomial system solvingReal geometryPolynomial matrix[ INFO.INFO-SC ] Computer Science [cs]/Symbolic Computation [cs.SC]Set (abstract data type)Matrix (mathematics)020901 industrial engineering & automationApplications0101 mathematicsAlgorithmMathematics
researchProduct

The Max-Product Algorithm Viewed as Linear Data-Fusion: A Distributed Detection Scenario

2019

In this paper, we disclose the statistical behavior of the max-product algorithm configured to solve a maximum a posteriori (MAP) estimation problem in a network of distributed agents. Specifically, we first build a distributed hypothesis test conducted by a max-product iteration over a binary-valued pairwise Markov random field and show that the decision variables obtained are linear combinations of the local log-likelihood ratios observed in the network. Then, we use these linear combinations to formulate the system performance in terms of the false-alarm and detection probabilities. Our findings indicate that, in the hypothesis test concerned, the optimal performance of the max-product a…

FOS: Computer and information sciencesfactor graphsComputer scienceComputer Science - Information TheoryMarkovin ketjut02 engineering and technologyMarkov random fieldsalgoritmit0202 electrical engineering electronic engineering information engineeringMaximum a posteriori estimationmax-product algorithmElectrical and Electronic EngineeringLinear combinationStatistical hypothesis testingdistributed systemsMarkov random fieldspectrum sensingApplied MathematicsNode (networking)Information Theory (cs.IT)linear data-fusionApproximation algorithm020206 networking & telecommunicationsComputer Science Applicationssum-product algorithmPairwise comparisonRandom variableAlgorithmstatistical inference
researchProduct

Fast Estimation of Diffusion Tensors under Rician noise by the EM algorithm

2016

Diffusion tensor imaging (DTI) is widely used to characterize, in vivo, the white matter of the central nerve system (CNS). This biological tissue contains much anatomic, structural and orientational information of fibers in human brain. Spectral data from the displacement distribution of water molecules located in the brain tissue are collected by a magnetic resonance scanner and acquired in the Fourier domain. After the Fourier inversion, the noise distribution is Gaussian in both real and imaginary parts and, as a consequence, the recorded magnitude data are corrupted by Rician noise. Statistical estimation of diffusion leads a non-linear regression problem. In this paper, we present a f…

FOS: Computer and information sciencesreduced computationGaussianModels NeurologicalDatasets as Topicta3112Statistics - ComputationStatistics - ApplicationsTime030218 nuclear medicine & medical imagingMethodology (stat.ME)Diffusion03 medical and health sciencessymbols.namesake0302 clinical medicineScoring algorithmRician fadingPrior probabilityExpectation–maximization algorithmImage Processing Computer-AssistedMaximum a posteriori estimationHumansApplications (stat.AP)Computer SimulationComputation (stat.CO)Statistics - MethodologyMathematicsta112Likelihood FunctionsGeneral NeuroscienceBrainEstimatormaximum likelihood estimatorFisher scoringMagnetic Resonance ImagingWhite MatterRician likelihoodDiffusion Tensor ImagingFourier transformNonlinear Dynamicssymbolsmaximum a posteriori estimatorAlgorithmAlgorithms030217 neurology & neurosurgerydata augmentation
researchProduct