BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Erik Aurell

Erik Aurell appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
cond-mat.stat-mechcond-mat.dis-nnGenomicsquant-phphysics.data-anQuantitative MethodsInformation Theorymath.ITComputational Complexityphysics.comp-phArtificial IntelligenceBiological PhysicsBiomoleculescond-mat.mes-hallcond-mat.softDistributed, Parallel, and Cluster Computinggr-qcmath-phmath.MPphysics.soc-phastro-phchao-dynComputationDiscrete Mathematicshep-thmath.CONetworking and Internet Architecturenlin.CDphysics.app-phPopulations and Evolutionq-fin.PRq-fin.TRstat.OT

Catalog footprint

What is connected

46works
33topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

46 published item(s)

preprint2022arXiv

Quantum information in Hawking radiation

In 1974 Steven Hawking showed that black holes emit thermal radiation, which eventually causes them to evaporate. The problem of the fate of information in this process is known as the "black hole information paradox". Two main types of resolution postulate either a fundamental loss of information in Nature -- hence the breakdown of quantum mechanics -- or some sort of new physics, e.g. quantum gravity, which guarantee the global preservation of unitarity. Here we explore the second possibility with the help of recent developments in continuous-variable quantum information. Concretely, we employ the solution to the Gaussian quantum marginal problem to show that the thermality of all individual Hawking modes is consistent with a global pure state of the radiation. Surprisingly, we find out that the mods of radiation of an astrophysical black hole are thermal until the very last burst. In contrast, the single-mode thermality of Hawking radiation originating from microscopic black holes, expected to evaporate through several quanta, is not excluded, though there are constraints on modes' frequencies. Our result paves the way towards a systematic study of multi-mode correlations in Hawking radiation.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Temporal epistasis inference from more than 3,500,000 SARS-CoV-2 Genomic Sequences

We use Direct Coupling Analysis (DCA) to determine epistatic interactions between loci of variability of the SARS-CoV-2 virus, segmenting genomes by month of sampling. We use full-length, high-quality genomes from the GISAID repository up to October 2021, in total over 3,500,000 genomes. We find that DCA terms are more stable over time than correlations, but nevertheless change over time as mutations disappear from the global population or reach fixation. Correlations are enriched for phylogenetic effects, and in particularly statistical dependencies at short genomic distances, while DCA brings out links at longer genomic distance. We discuss the validity of a DCA analysis under these conditions in terms of a transient Quasi-Linkage Equilibrium state. We identify putative epistatic interaction mutations involving loci in Spike.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The double doors of the horizon

In statistical mechanics entropy is a measure of disorder obeying Boltzmann's formula $S=\log{\cal N}$, where ${\cal N}$ is the accessible phase space volume. In black hole thermodynamics one associates to a black hole an entropy Bekenstein-Hawking $S_{BH}$. It is well known that $S_{BH}$ is very large for astrophysical black holes, much larger than any collection of material objects that could have given rise to the black hole. If $S_{BH}$ is an entropy the question is thus what is the corresponding ${\cal N}$, and how come this very large phase space volume is only opened up to the universe by a gravitational collapse, which from another perspective looks like a massive loss of possibilities. I advance a hypothesis that the very large increase in entropy can perhaps be understood as an effect of classical gravity, which eventually bottoms out when quantum gravity comes into play. I compare and discuss a selection of the very rich literature around these questions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fröhlich-coupled qubits interacting with fermionic baths

We consider a macroscopic quantum system such as a qubit, interacting with a bath of fermions as in the Fröhlich polaron model. The interaction Hamiltonian is thus linear in the macroscopic system variable, and bilinear in the fermions. Using the recently developed extension of Feynman-Vernon theory to non-harmonic baths we evaluate quadratic and the quartic terms in the influence action. We find that for this model the quartic term vanish by symmetry arguments. Although the influence of the bath on the system is of the same form as from bosonic harmonic oscillators up to effects to sixth order in the system-bath interaction, the temperature dependence is nevertheless rather different, unless rather contrived models are considered.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Global analysis of more than 50,000 SARS-Cov-2 genomes reveals epistasis between 8 viral genes

Genome-wide epistasis analysis is a powerful tool to infer gene interactions, which can guide drug and vaccine development and lead to a deeper understanding of microbial pathogenesis. We have considered all complete SARS-CoV-2 genomes deposited in the GISAID repository until \textbf{four} different cut-off dates, and used Direct Coupling Analysis together with an assumption of Quasi-Linkage Equilibrium to infer epistatic contributions to fitness from polymorphic loci. We find \textbf{eight} interactions, of which three between pairs where one locus lies in gene ORF3a, both loci holding non-synonymous mutations. We also find interactions between two loci in gene nsp13, both holding non-synonymous mutations, and four interactions involving one locus holding a synonymous mutation. Altogether we infer interactions between loci in viral genes ORF3a and nsp2, nsp12 and nsp6, between ORF8 and nsp4, and between loci in genes nsp2, nsp13 and nsp14. The paper opens the prospect to use prominent epistatically linked pairs as a starting point to search for combinatorial weaknesses of recombinant viral pathogens.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Inferring genetic fitness from genomic data

The genetic composition of a naturally developing population is considered as due to mutation, selection, genetic drift and recombination. Selection is modeled as single-locus terms (additive fitness) and two-loci terms (pairwise epistatic fitness). The problem is posed to infer epistatic fitness from population-wide whole-genome data from a time series of a developing population. We generate such data in silico, and show that in the Quasi-Linkage Equilibrium (QLE) phase of Kimura, Neher and Shraiman, that pertains at high enough recombination rates and low enough mutation rates, epistatic fitness can be quantitatively correctly inferred using inverse Ising/Potts methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Inverse Ising techniques to infer underlying mechanisms from data

As a problem in data science the inverse Ising (or Potts) problem is to infer the parameters of a Gibbs-Boltzmann distributions of an Ising (or Potts) model from samples drawn from that distribution. The algorithmic and computational interest stems from the fact that this inference task cannot be done efficiently by the maximum likelihood criterion, since the normalizing constant of the distribution (the partition function) can not be calculated exactly and efficiently. The practical interest on the other hand flows from several outstanding applications, of which the most well known has been predicting spatial contacts in protein structures from tables of homologous protein sequences. Most applications to date have been to data that has been produced by a dynamical process which, as far as it is known, cannot be expected to satisfy detailed balance. There is therefore no a priori reason to expect the distribution to be of the Gibbs-Boltzmann type, and no a priori reason to expect that inverse Ising (or Potts) techniques should yield useful information. In this review we discuss two types of problems where progress nevertheless can be made. We find that depending on model parameters there are phases where, in fact, the distribution is close to Gibbs-Boltzmann distribution, a non-equilibrium nature of the under-lying dynamics notwithstanding. We also discuss the relation between inferred Ising model parameters and parameters of the underlying dynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large Deviations and Fluctuation Theorem for the Quantum Heat Current

We study the heat current flowing between two baths consisting of harmonic oscillators interacting with a qubit through a spin-boson coupling. An explicit expression for the generating function of the total heat flowing between the hot and cold baths is derived by evaluating the corresponding Feynman-Vernon path integral under the non-interacting blip approximation (NIBA). This generating function satisfies the Gallavotti-Cohen fluctuation theorem, both before and after performing the NIBA. We also verify that the heat conductivity is proportional to the variance of the heat current, retrieving the well known fluctuation dissipation relation. Finally, we present numerical results for the heat current.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

An operator derivation of the Feynman-Vernon theory, with applications to the generating function of bath energy changes and to anharmonic baths

We present a derivation of the Feynman-Vernon approach to open quantum systems in the language of super-operators. We show that this gives a new and more direct derivation of the generating function of energy changes in a bath, or baths. This generating function is given by a Feynman-Vernon-like influence functional, with only time shifts in some of the kernels. We further show that the approach can be extended to anharmonic baths by an expansion in cumulants. Every non-zero cumulant of certain environment correlation functions thus gives a kernel in a higher-order term in the Feynman-Vernon action.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

An observation of circular RNAs in bacterial RNA-seq data

Circular RNAs (circRNAs) are a class of RNA with an important role in micro RNA (miRNA) regulation recently discovered in Human and various other eukaryotes as well as in archaea. Here, we have analyzed RNA-seq data obtained from {\it Enterococcus faecalis} and {\it Escherichia coli} in a way similar to previous studies performed on eukaryotes. We report observations of circRNAs in RNA-seq data that are reproducible across multiple experiments performed with different protocols or growth conditions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On one-step replica symmetry breaking in the Edwards-Anderson spin glass model

We consider a one-step replica symmetry breaking description of the Edwards-Anderson spin glass model in 2D. The ingredients of this description are a Kikuchi approximation to the free energy and a second-level statistical model built on the extremal points of the Kikuchi approximation, which are also fixed points of a Generalized Belief Propagation (GBP) scheme. We show that a generalized free energy can be constructed where these extremal points are exponentially weighted by their Kikuchi free energy and a Parisi parameter $y$, and that the Kikuchi approximation of this generalized free energy leads to second-level, one-step replica symmetry breaking (1RSB), GBP equations. We then proceed analogously to Bethe approximation case for tree-like graphs, where it has been shown that 1RSB Belief Propagation equations admit a Survey Propagation solution. We discuss when and how the one-step-replica symmetry breaking GBP equations that we obtain also allow a simpler class of solutions which can be interpreted as a class of Generalized Survey Propagation equations for the single instance graph case.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Dynamic message-passing approach for kinetic spin models with reversible dynamics

A method to approximately close the dynamic cavity equations for synchronous reversible dynamics on a locally tree-like topology is presented. The method builds on $(a)$ a graph expansion to eliminate loops from the normalizations of each step in the dynamics, and $(b)$ an assumption that a set of auxilary probability distributions on histories of pairs of spins mainly have dependencies that are local in time. The closure is then effectuated by projecting these probability distributions on $n$-step Markov processes. The method is shown in detail on the level of ordinary Markov processes ($n=1$), and outlined for higher-order approximations ($n>1$). Numerical validations of the technique are provided for the reconstruction of the transient and equilibrium dynamics of the kinetic Ising model on a random graph with arbitrary connectivity symmetry.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Bulk and The Tail of Minimal Absent Words in Genome Sequences

Minimal absent words (MAW) of a genomic sequence are subsequences that are absent themselves but the subwords of which are all present in the sequence. The characteristic distribution of genomic MAWs as a function of their length has been observed to be qualitatively similar for all living organisms, the bulk being rather short, and only relatively few being long. It has been an open issue whether the reason behind this phenomenon is statistical or reflects a biological mechanism, and what biological information is contained in absent words. In this work we demonstrate that the bulk can be described by a probabilistic model of sampling words from random sequences, while the tail of long MAWs is of biological origin. We introduce the novel concept of a core of a minimal absent word, which are sequences present in the genome and closest to a given MAW. We show that in bacteria and yeast the cores of the longest MAWs, which exist in two or more copies, are located in highly conserved regions the most prominent example being ribosomal RNAs (rRNAs). We also show that while the distribution of the cores of long MAWs is roughly uniform over these genomes on a coarse-grained level, on a more detailed level it is strongly enhanced in 3' untranslated regions (UTRs) and, to a lesser extent, also in 5' UTRs. This indicates that MAWs and associated MAW cores correspond to fine-tuned evolutionary relationships, and suggest that they can be more widely used as markers for genomic complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Time reversals of irreversible quantum maps

We introduce the notion of time reversal in open quantum systems as represented by linear quantum operations, and a related generalization of classical entropy production in the environment. This functional is the ratio of the probability to observe a transition between two states under the forward and the time reversed dynamics, and leads, as in the classical case, to fluctuation relations as tautological identities. As in classical dynamics in contact with a heat bath, time reversal is not unique, and we discuss several possibilities. For any bistochastic map its dual map preserves the trace and describes a legitimate dynamics reversed in time, in that case the entropy production in the environment vanishes. For a generic stochastic map we construct a simple quantum operation which can be interpreted as a time reversal. For instance, the decaying channel, which sends the excited state into the ground state with a certain probability, can be reversed into the channel transforming the ground state into the excited state with the same probability.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fast pseudolikelihood maximization for direct-coupling analysis of protein structure from many homologous amino-acid sequences

Direct-Coupling Analysis is a group of methods to harvest information about coevolving residues in a protein family by learning a generative model in an exponential family from data. In protein families of realistic size, this learning can only be done approximately, and there is a trade-off between inference precision and computational speed. We here show that an earlier introduced $l_2$-regularized pseudolikelihood maximization method called plmDCA can be modified as to be easily parallelizable, as well as inherently faster on a single processor, at negligible difference in accuracy. We test the new incarnation of the method on 148 protein families from the Protein Families database (PFAM), one of the largest tests of this class of algorithms to date.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improving contact prediction along three dimensions

Correlation patterns in multiple sequence alignments of homologous proteins can be exploited to infer information on the three-dimensional structure of their members. The typical pipeline to address this task, which we in this paper refer to as the three dimensions of contact prediction, is to: (i) filter and align the raw sequence data representing the evolutionarily related proteins; (ii) choose a predictive model to describe a sequence alignment; (iii) infer the model parameters and interpret them in terms of structural properties, such as an accurate contact map. We show here that all three dimensions are important for overall prediction success. In particular, we show that it is possible to improve significantly along the second dimension by going beyond the pair-wise Potts models from statistical physics, which have hitherto been the focus of the field. These (simple) extensions are motivated by multiple sequence alignments often containing long stretches of gaps which, as a data feature, would be rather untypical for independent samples drawn from a Potts model. Using a large test set of proteins we show that the combined improvements along the three dimensions are as large as any reported to date.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Perturbative large deviation analysis of non-equilibrium dynamics

Macroscopic fluctuation theory has shown that a wide class of non-equilibrium stochastic dynamical systems obey a large deviation principle, but except for a few one-dimensional examples these large deviation principles are in general not known in closed form. We consider the problem of constructing successive approximations to an (unknown) large deviation functional and show that the non-equilibrium probability distribution the takes a Gibbs-Boltzmann form with a set of auxiliary (non-physical) energy functions. The expectation values of these auxiliary energy functions and their conjugate quantities satisfy a closed system of equations which can imply a considerable reduction of dimensionality of the dynamics. We show that the accuracy of the approximations can be tested self-consistently without solving the full non- equilibrium equations. We test the general procedure on the simple model problem of a relaxing 1D Ising chain.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

SEK: Sparsity exploiting $k$-mer-based estimation of bacterial community composition

Motivation: Estimation of bacterial community composition from a high-throughput sequenced sample is an important task in metagenomics applications. Since the sample sequence data typically harbors reads of variable lengths and different levels of biological and technical noise, accurate statistical analysis of such data is challenging. Currently popular estimation methods are typically very time consuming in a desktop computing environment. Results: Using sparsity enforcing methods from the general sparse signal processing field (such as compressed sensing), we derive a solution to the community composition estimation problem by a simultaneous assignment of all sample reads to a pre-processed reference database. A general statistical model based on kernel density estimation techniques is introduced for the assignment task and the model solution is obtained using convex optimization tools. Further, we design a greedy algorithm solution for a fast solution. Our approach offers a reasonably fast community composition estimation method which is shown to be more robust to input data variation than a recently introduced related method. Availability: A platform-independent Matlab implementation of the method is freely available at http://www.ee.kth.se/ctsoftware; source code that does not require access to Matlab is currently being tested and will be made available later through the above website.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The stochastic thermodynamics of a rotating Brownian particle in a gradient flow

We compute the entropy production engendered in the environment from a single Brownian particle which moves in a mean flow, and show that it corresponds in expectation to classical near-equilibrium entropy production in the surrounding fluid with specific mesoscopic transport coefficients. With temperature gradient, extra terms are found which results from the nonlinear interaction between the particle and the non-equilibrated environment. The calculations are carried out in the multi-time formalism and in the advection-dissipation limit where the Stokes number (St) of the flow tends to zero and the Peclet number (Pe) diverges but the combination St times Pe remains constant.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Whole genome mapping of 5' RNA ends in bacteria by tagged sequencing : A comprehensive view in Enterococcus faecalis

Enterococcus faecalis is the third cause of nosocomial infections. To obtain the first comprehensive view of transcriptional organizations in this bacterium, we used a modified RNA-seq approach enabling to discriminate primary from processed 5'RNA ends. We also validated our approach by confirming known features in Escherichia coli. We mapped 559 transcription start sites and 352 processing sites in E. faecalis. A blind motif search retrieved canonical features of SigA- and SigN-dependent promoters preceding TSSs mapped. We discovered 95 novel putative regulatory RNAs, small- and antisense RNAs, and 72 transcriptional antisense organisations. Presented data constitute a significant insight into bacterial RNA landscapes and a step towards the inference of regulatory processes at transcriptional and post-transcriptional levels in a comprehensive manner.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A novel local search based on variable-focusing for random K-SAT

We introduce a new local search algorithm for satisfiability problems. Usual approaches focus uniformly on unsatisfied clauses. The new method works by picking uniformly random variables in unsatisfied clauses. A Variable-based Focused Metropolis Search (V-FMS) is then applied to random 3-SAT. We show that it is quite comparable in performance to the clause-based FMS. Consequences for algorithmic design are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Improved contact prediction in proteins: Using pseudolikelihoods to infer Potts models

Spatially proximate amino acids in a protein tend to coevolve. A protein's three-dimensional (3D) structure hence leaves an echo of correlations in the evolutionary record. Reverse engineering 3D structures from such correlations is an open problem in structural biology, pursued with increasing vigor as more and more protein sequences continue to fill the data banks. Within this task lies a statistical inference problem, rooted in the following: correlation between two sites in a protein sequence can arise from firsthand interaction but can also be network-propagated via intermediate sites; observed correlation is not enough to guarantee proximity. To separate direct from indirect interactions is an instance of the general problem of inverse statistical mechanics, where the task is to learn model parameters (fields, couplings) from observables (magnetizations, correlations, samples) in large systems. In the context of protein sequences, the approach has been referred to as direct-coupling analysis. Here we show that the pseudolikelihood method, applied to 21-state Potts models describing the statistical properties of families of evolutionarily related proteins, significantly outperforms existing approaches to the direct-coupling analysis, the latter being based on standard mean-field techniques. This improved performance also relies on a modified score for the coupling strength. The results are verified using known crystal structures of specific sequence instances of various protein families. Code implementing the new method can be found at http://plmdca.csc.kth.se/.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lognormality and oscillations in the coverage of high-throughput transcriptomic data towards gene ends

High-throughput transcriptomics experiments have reached the stage where the count of the number of reads alignable to a given position can be treated as an almost-continuous signal. This allows to ask questions of biophysical/biotechnical nature, but which may still have biological implications. Here we show that when sequencing RNA fragments from one end, as it is the case on most platforms, an oscillation in the read count is observed at the other end. We further show that these oscillations can be well described by Kolmogorov's 1941 broken stick model. We investigate how the model can be used to improve predictions of gene ends (3' transcript ends) but conclude that with present data the improvement is only marginal. The results highlight subtle effects in high-throughput transcriptomics experiments which do not have a biological origin, but which may still be used to obtain biological information.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maximum likelihood reconstruction for Ising models with asynchronous updates

We describe how the couplings in an asynchronous kinetic Ising model can be inferred. We consider two cases, one in which we know both the spin history and the update times and one in which we only know the spin history. For the first case, we show that one can average over all possible choices of update times to obtain a learning rule that depends only on spin correlations and can also be derived from the equations of motion for the correlations. For the second case, the same rule can be derived within a further decoupling approximation. We study all methods numerically for fully asymmetric Sherrington-Kirkpatrick models, varying the data length, system size, temperature, and external field. Good convergence is observed in accordance with the theoretical expectations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Optimal stochastic transport in inhomogeneous thermal environments

We consider optimization of the average entropy production in inhomogeneous temperature environments within the framework of stochastic thermodynamics. For systems modeled by Langevin equations (e.g. a colloidal particle in a heat bath) it has been recently shown that a space dependent temperature breaks the time reversal symmetry of the fast velocity degrees of freedom resulting in an anomalous contribution to the entropy production of the overdamped dynamics. We show that optimization of entropy production is determined by an auxiliary deterministic problem describing motion on a curved manifold in a potential. The "anomalous contribution" to entropy plays the role of the potential and the inverse of the diffusion tensor is the metric. We also find that entropy production is not minimized by adiabatically slow, quasi-static protocols but there is a finite optimal duration for the transport process. As an example we discuss the case of a linearly space dependent diffusion coefficient.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Witness of unsatisfiability for a random 3-satisfiability formula

The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density $α$ exceeds a critical value $α_s \approx 4.267$. However, rigorously proving the unsatisfiability of a given large 3-SAT instance is extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses) can in principle be constructed when the clause density $α> 19$. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when $α$ scales at least linearly with the variable number $N$, but the focused local search algorithm works for clause densty $α> c N^{b}$ with $b \approx 0.59$ and prefactor $c \approx 8$. The exponent $b$ can be further decreased by enlarging the single parameter $S$ of the focused local search algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Analysis of Sparse Representations Using Bi-Orthogonal Dictionaries

The sparse representation problem of recovering an N dimensional sparse vector x from M < N linear observations y = Dx given dictionary D is considered. The standard approach is to let the elements of the dictionary be independent and identically distributed (IID) zero-mean Gaussian and minimize the l1-norm of x under the constraint y = Dx. In this paper, the performance of l1-reconstruction is analyzed, when the dictionary is bi-orthogonal D = [O1 O2], where O1,O2 are independent and drawn uniformly according to the Haar measure on the group of orthogonal M x M matrices. By an application of the replica method, we obtain the critical conditions under which perfect l1-recovery is possible with bi-orthogonal dictionaries.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Anomalous thermodynamics at the micro-scale

Particle motion at the micro-scale is an incessant tug-of-war between thermal fluctuations and applied forces on one side, and the strong resistance exerted by fluid viscosity on the other. Friction is so strong that completely neglecting inertia - the overdamped approximation - gives an excellent effective description of the actual particle mechanics. In sharp contrast with this result, here we show that the overdamped approximation dramatically fails when thermodynamic quantities such as the entropy production in the environment is considered, in presence of temperature gradients. In the limit of vanishingly small, yet finite inertia, we find that the entropy production is dominated by a contribution that is anomalous, i.e. has no counterpart in the overdamped approximation. This phenomenon, that we call entropic anomaly, is due to a symmetry-breaking that occurs when moving to the small, finite inertia limit. Strong production of anomalous entropy is traced back to intense sweeps down the temperature gradient.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Dynamic mean-field and cavity methods for diluted Ising systems

We compare dynamic mean-field and dynamic cavity as methods to describe the stationary states of dilute kinetic Ising models. We compute dynamic mean-field theory by expanding in interaction strength to third order, and compare to the exact dynamic mean-field theory for fully asymmetric networks. We show that in diluted networks the dynamic cavity method generally predicts magnetizations of individual spins better than both first order ("naive") and second order ("TAP") dynamic mean field theory.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Inverse Ising inference using all the data

We show that a method based on logistic regression, using all the data, solves the inverse Ising problem far better than mean-field calculations relying only on sample pairwise correlation functions, while still computationally feasible for hundreds of nodes. The largest improvement in reconstruction occurs for strong interactions. Using two examples, a diluted Sherrington-Kirkpatrick model and a two-dimensional lattice, we also show that interaction topologies can be recovered from few samples with good accuracy and that the use of $l_1$-regularization is beneficial in this process, pushing inference abilities further into low-temperature regimes.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A message-passing scheme for non-equilibrium stationary states

We study stationary states in a diluted asymmetric (kinetic) Ising model. We apply the recently introduced dynamic cavity method to compute magnetizations of these stationary states. Depending on the update rule, different versions of the dynamic cavity method apply. We here study synchronous updates and random sequential updates, and compare local properties computed by the dynamic cavity method to numerical simulations. Using both types of updates, the dynamic cavity method is highly accurate at high enough temperatures. At low enough temperatures, for sequential updates the dynamic cavity method tends to a fixed point, but which does not agree with numerical simulations, while for parallel updates, the dynamic cavity method may display cyclic behavior. When it converges and is accurate, the dynamic cavity method offers a huge speed-up compared to Monte Carlo, particularly for large systems.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Boundary layers in stochastic thermodynamics

We study the problem of optimizing released heat or dissipated work in stochastic thermodynamics. In the overdamped limit these functionals have singular solutions, previously interpreted as protocol jumps. We show that a regularization, penalizing a properly defined acceleration, changes the jumps into boundary layers of finite width. We show that in the limit of vanishing boundary layer width no heat is dissipated in the boundary layer, while work can be done. We further give a new interpretation of the fact that the optimal protocols in the overdamped limit are given by optimal deterministic transport (Burgers equation).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Three lemmas on the dynamic cavity method

We study the dynamic cavity method for dilute kinetic Ising models with synchronous update rules. For the parallel update rule we find for fully asymmetric models that the dynamic cavity equations reduce to a Markovian dynamics of the (time-dependent) marginal probabilities. For the random sequential update rule, also an instantiation of a synchronous update rule, we find on the other hand that the dynamic cavity equations do not reduce to a Markovian dynamics, unless an additional assumption of time factorization is introduced. For symmetric models we show that a fixed point of ordinary Belief propagation is also a fixed point of the dynamic cavity equations in the time factorized approximation. For clarity, the conclusions of the paper are formulated as three lemmas.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Bounds on Threshold of Regular Random $k$-SAT

We consider the regular model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad et. al. We derive an upper bound on the satisfiability threshold and NAE-satisfiability threshold for regular random $k$-SAT for any $k \geq 3$. We show that these bounds matches with the corresponding bound for the uniform model of formula generation. We derive lower bound on the threshold by applying the second moment method to the number of satisfying assignments. For large $k$, we note that the obtained lower bounds on the threshold of a regular random formula converges to the lower bound obtained for the uniform model. Thus, we answer the question posed in \cite{AcM06} regarding the performance of the second moment method for regular random formulas.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Bounds on Thresholds Related to Maximum Satisfiability of Regular Random Formulas

We consider the regular balanced model of formula generation in conjunctive normal form (CNF) introduced by Boufkhad, Dubois, Interian, and Selman. We say that a formula is $p$-satisfying if there is a truth assignment satisfying $1-2^{-k}+p 2^{-k}$ fraction of clauses. Using the first moment method we determine upper bound on the threshold clause density such that there are no $p$-satisfying assignments with high probability above this upper bound. There are two aspects in deriving the lower bound using the second moment method. The first aspect is, given any $p \in (0,1)$ and $k$, evaluate the lower bound on the threshold. This evaluation is numerical in nature. The second aspect is to derive the lower bound as a function of $p$ for large enough $k$. We address the first aspect and evaluate the lower bound on the $p$-satisfying threshold using the second moment method. We observe that as $k$ increases the lower bound seems to converge to the asymptotically derived lower bound for uniform model of formula generation by Achlioptas, Naor, and Peres.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dynamics and Performance of Susceptibility Propagation on Synthetic Data

We study the performance and convergence properties of the Susceptibility Propagation (SusP) algorithm for solving the Inverse Ising problem. We first study how the temperature parameter (T) in a Sherrington-Kirkpatrick model generating the data influences the performance and convergence of the algorithm. We find that at the high temperature regime (T>4), the algorithm performs well and its quality is only limited by the quality of the supplied data. In the low temperature regime (T<4), we find that the algorithm typically does not converge, yielding diverging values for the couplings. However, we show that by stopping the algorithm at the right time before divergence becomes serious, good reconstruction can be achieved down to T~2. We then show that dense connectivity, loopiness of the connectivity, and high absolute magnetization all have deteriorating effects on the performance of the algorithm. When absolute magnetization is high, we show that other methods can be work better than SusP. Finally, we show that for neural data with high absolute magnetization, SusP performs less well than TAP inversion.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Network inference using asynchronously updated kinetic Ising Model

Network structures are reconstructed from dynamical data by respectively naive mean field (nMF) and Thouless-Anderson-Palmer (TAP) approximations. For TAP approximation, we use two methods to reconstruct the network: a) iteration method; b) casting the inference formula to a set of cubic equations and solving it directly. We investigate inference of the asymmetric Sherrington- Kirkpatrick (S-K) model using asynchronous update. The solutions of the sets cubic equation depend of temperature T in the S-K model, and a critical temperature Tc is found around 2.1. For T < Tc, the solutions of the cubic equation sets are composed of 1 real root and two conjugate complex roots while for T > Tc there are three real roots. The iteration method is convergent only if the cubic equations have three real solutions. The two methods give same results when the iteration method is convergent. Compared to nMF, TAP is somewhat better at low temperatures, but approaches the same performance as temperature increase. Both methods behave better for longer data length, but for improvement arises, TAP is well pronounced.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal protocols and optimal transport in stochastic thermodynamics

Thermodynamics of small systems has become an important field of statistical physics. They are driven out of equilibrium by a control, and the question is naturally posed how such a control can be optimized. We show that optimization problems in small system thermodynamics are solved by (deterministic) optimal transport, for which very efficient numerical methods have been developed, and of which there are applications in Cosmology, fluid mechanics, logistics, and many other fields. We show, in particular, that minimizing expected heat released or work done during a non-equilibrium transition in finite time is solved by Burgers equation of Cosmology and mass transport by the Burgers velocity field. Our contribution hence considerably extends the range of solvable optimization problems in small system thermodynamics.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Accuracy of Tree-based Counting in Dynamic Networks

Tree-based protocols are ubiquitous in distributed systems. They are flexible, they perform generally well, and, in static conditions, their analysis is mostly simple. Under churn, however, node joins and failures can have complex global effects on the tree overlays, making analysis surprisingly subtle. To our knowledge, few prior analytic results for performance estimation of tree based protocols under churn are currently known. We study a simple Bellman-Ford-like protocol which performs network size estimation over a tree-shaped overlay. A continuous time Markov model is constructed which allows key protocol characteristics to be estimated, including the expected number of nodes at a given (perceived) distance to the root and, for each such node, the expected (perceived) size of the subnetwork rooted at that node. We validate the model by simulation, using a range of network sizes, node degrees, and churn-to-protocol rates, with convincing results.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Gaussian Belief with dynamic data and in dynamic network

In this paper we analyse Belief Propagation over a Gaussian model in a dynamic environment. Recently, this has been proposed as a method to average local measurement values by a distributed protocol ("Consensus Propagation", Moallemi & Van Roy, 2006), where the average is available for read-out at every single node. In the case that the underlying network is constant but the values to be averaged fluctuate ("dynamic data"), convergence and accuracy are determined by the spectral properties of an associated Ruelle-Perron-Frobenius operator. For Gaussian models on Erdos-Renyi graphs, numerical computation points to a spectral gap remaining in the large-size limit, implying exceptionally good scalability. In a model where the underlying network also fluctuates ("dynamic network"), averaging is more effective than in the dynamic data case. Altogether, this implies very good performance of these methods in very large systems, and opens a new field of statistical physics of large (and dynamic) information systems.

0 citations0 reviewsNo code linkedOpen access
preprint2007arXiv

An Analytical Study of a Structured Overlay in the presence of Dynamic Membership

In this paper we present an analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a fluid model approach to describe steady-state or transient phenomena, and apply it to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of the probability of network disconnection as well as the fraction of failed or incorrect successor and finger pointers. We show how we can use these quantities to predict both the performance and consistency of lookups under churn. All theoretical predictions match simulation results. The analysis includes both features that are generic to structured overlays deploying a ring as well as Chord-specific details, and opens the door to a systematic comparative analysis of, at least, ring-based structured overlay systems under churn.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Behavior of heuristics and state space structure near SAT/UNSAT transition

We study the behavior of ASAT, a heuristic for solving satisfiability problems by stochastic local search near the SAT/UNSAT transition. The heuristic is focused, i.e. only variables in unsatisfied clauses are updated in each step, and is significantly simpler, while similar to, walksat or Focused Metropolis Search. We show that ASAT solves instances as large as one million variables in linear time, on average, up to 4.21 clauses per variable for random 3SAT. For K higher than 3, ASAT appears to solve instances at the ``FRSB threshold'' in linear time, up to K=7.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Optimal hedging of Derivatives with transaction costs

We investigate the optimal strategy over a finite time horizon for a portfolio of stock and bond and a derivative in an multiplicative Markovian market model with transaction costs (friction). The optimization problem is solved by a Hamilton-Bellman-Jacobi equation, which by the verification theorem has well-behaved solutions if certain conditions on a potential are satisfied. In the case at hand, these conditions simply imply arbitrage-free ("Black-Scholes") pricing of the derivative. While pricing is hence not changed by friction allow a portfolio to fluctuate around a delta hedge. In the limit of weak friction, we determine the optimal control to essentially be of two parts: a strong control, which tries to bring the stock-and-derivative portfolio towards a Black-Scholes delta hedge; and a weak control, which moves the portfolio by adding or subtracting a Black-Scholes hedge. For simplicity we assume growth-optimal investment criteria and quadratic friction.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

On the dynamics of a self-gravitating medium with random and non-random initial conditions

The dynamics of a one-dimensional self-gravitating medium, with initial density almost uniform is studied. Numerical experiments are performed with ordered and with Gaussian random initial conditions. The phase space portraits are shown to be qualitatively similar to shock waves, in particular with initial conditions of Brownian type. The PDF of the mass distribution is investigated.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Financial Friction and Multiplicative Markov Market Game

We study long-term growth-optimal strategies on a simple market with linear proportional transaction costs. We show that several problems of this sort can be solved in closed form, and explicit the non-analytic dependance of optimal strategies and expected frictional losses of the friction parameter. We present one derivation in terms of invariant measures of drift-diffusion processes (Fokker- Planck approach), and one derivation using the Hamilton-Jacobi-Bellman equation of optimal control theory. We also show that a significant part of the results can be derived without computation by a kind of dimensional analysis. We comment on the extension of the method to other sources of uncertainty, and discuss what conclusions can be drawn about the growth-optimal criterion as such.

0 citations0 reviewsNo code linkedOpen access