Search

Noiseless compressive sensing is a protocol that enables undersampling and later recovery of a signal without loss of information. This compression is possible because the signal is usually sufficiently sparse in a given basis. Currently, the algorithm offering the best tradeoff between compression rate, robustness, and speed for compressive sensing is the LASSO (l1-norm bias) algorithm. However, many studies have pointed out the possibility that the implementation of lp-norms biases, with p smaller than one, could give better performance while sacrificing convexity. In this work, we focus specifically on the extreme case of the l0-based reconstruction, a task that is complicated by the discontinuity of the loss. In the first part of the paper, we describe via statistical physics methods, and in particular the replica method, how the solutions to this optimization problem are arranged in a clustered structure. We observe two distinct regimes: one at low compression rate where the signal can be recovered exactly, and one at high compression rate where the signal cannot be recovered accurately. In the second part, we present two message-passing algorithms based on our first results for the l0-norm optimization problem. The proposed algorithms are able to recover the signal at compression rates higher than the ones achieved by LASSO while being computationally efficient.

The third edition of the "international - Traveling Workshop on Interactions between Sparse models and Technology" (iTWIST) took place in Aalborg, the 4th largest city in Denmark situated beautifully in the northern part of the country, from the 24th to 26th of August 2016. The workshop venue was at the Aalborg University campus. One implicit objective of this biennial workshop is to foster collaboration between international scientific teams by disseminating ideas through both specific oral/poster presentations and free discussions. For this third edition, iTWIST'16 gathered about 50 international participants and features 8 invited talks, 12 oral presentations, and 12 posters on the following themes, all related to the theory, application and generalization of the "sparsity paradigm": Sparsity-driven data sensing and processing (e.g., optics, computer vision, genomics, biomedical, digital communication, channel estimation, astronomy); Application of sparse models in non-convex/non-linear inverse problems (e.g., phase retrieval, blind deconvolution, self calibration); Approximate probabilistic inference for sparse problems; Sparse machine learning and inference; "Blind" inverse problems and dictionary learning; Optimization for sparse modelling; Information theory, geometry and randomness; Sparsity? What's next? (Discrete-valued signals; Union of low-dimensional spaces, Cosparsity, mixed/group norm, model-based, low-complexity models, ...); Matrix/manifold sensing/processing (graph, low-rank approximation, ...); Complexity/accuracy tradeoffs in numerical methods/optimization; Electronic/optical compressive sensors (hardware)., Comment: 69 pages, 22 extended abstracts, iTWIST'16 website: http://www.itwist16.es.aau.dk

We study first-order quantum phase transitions in models where the mean-field traitment is exact, and the exponentially fast closure of the energy gap with the system size at the transition. We consider exactly solvable ferromagnetic models, and show that they reduce to the Grover problem in a particular limit. We compute the coefficient in the exponential closure of the gap using an instantonic approach, and discuss the (dire) consequences for quantum annealing., Comment: 6 pages, 3 figures

We present a study of the phase diagram of a random optimization problem in presence of quantum fluctuations. Our main result is the characterization of the nature of the phase transition, which we find to be a first-order quantum phase transition. We provide evidence that the gap vanishes exponentially with the system size at the transition. This indicates that the Quantum Adiabatic Algorithm requires a time growing exponentially with system size to find the ground state of this problem., Comment: 4 pages, 4 figures; final version accepted on Phys.Rev.Lett

The granular jamming transition is experimentally investigated in a two-dimensional system of frictional, bi-dispersed disks subject to quasi-static, uniaxial compression at zero granular temperature. Currently accepted results show the jamming transition occurs at a critical packing fraction $\phi_c$. In contrast, we observe the first compression cycle exhibits {\it fragility} - metastable configuration with simultaneous jammed and un-jammed clusters - over a small interval in packing fraction ($\phi_1 < \phi < \phi_2$). The fragile state separates the two conditions that define $\phi_c$ with an exponential rise in pressure starting at $\phi_1$ and an exponential fall in disk displacements ending at $\phi_2$. The results are explained through a percolation mechanism of stressed contacts where cluster growth exhibits strong spatial correlation with disk displacements. Measurements with several disk materials of varying elastic moduli $E$ and friction coefficients $\mu$, show friction directly controls the start of the fragile state, but indirectly controls the exponential slope. Additionally, we experimentally confirm recent predictions relating the dependence of $\phi_c$ on $\mu$. Under repetitive loading (compression), the system exhibits hysteresis in pressure, and the onset $\phi_c$ increases slowly with repetition number. This friction induced hysteretic creep is interpreted as the granular pack's evolution from a metastable to an eventual structurally stable configuration. It is shown to depend upon the quasi-static step size $\Delta \phi$ which provides the only perturbative mechanism in the experimental protocol, and the friction coefficient $\mu$ which acts to stabilize the pack., Comment: 12 pages, 10 figures

Methods to extract information from the tracking of mobile objects/particles have broad interest in biological and physical sciences. Techniques based on simple criteria of proximity in time-consecutive snapshots are useful to identify the trajectories of the particles. However, they become problematic as the motility and/or the density of the particles increases due to uncertainties on the trajectories that particles followed during the images' acquisition time. Here, we report an efficient method for learning parameters of the dynamics of the particles from their positions in time-consecutive images. Our algorithm belongs to the class of message-passing algorithms, known in computer science, information theory and statistical physics as Belief Propagation (BP). The algorithm is distributed, thus allowing parallel implementation suitable for computations on multiple machines without significant inter-machine overhead. We test our method on the model example of particle tracking in turbulent flows, which is particularly challenging due to the strong transport that those flows produce. Our numerical experiments show that the BP algorithm compares in quality with exact Markov Chain Monte-Carlo algorithms, yet BP is far superior in speed. We also suggest and analyze a random-distance model that provides theoretical justification for BP accuracy. Methods developed here systematically formulate the problem of particle tracking and provide fast and reliable tools for its extensive range of applications., Comment: 18 pages, 9 figures

Recent ideas based on the properties of assemblies of frictionless particles in mechanical equilibrium provide a perspective of amorphous systems different from that offered by the traditional approach originating in liquid theory. The relation, if any, between these two points of view, and the relevance of the former to the glass phase, has been difficult to ascertain. In this paper we introduce a model for which both theories apply strictly: it exhibits on the one hand an ideal glass transition and on the other `jamming' features (fragility, soft modes) virtually identical to that of real systems. This allows us to disentangle the different contents and domains of applicability of the two physical phenomena., Comment: 4 pages, 6 figures Modified content, new figure

We address the question of geometrical as well as energetic properties of local excitations in mean field Ising spin glasses. We study analytically the Random Energy Model and numerically a dilute mean field model, first on tree-like graphs, equivalent to a replica symmetric computation, and then directly on finite connectivity random lattices. In the first model, characterized by a discontinuous replica symmetry breaking, we found that the energy of finite volume excitation is infinite whereas in the dilute mean field model, described by a continuous replica symmetry breaking, it slowly decreases with sizes and saturates at a finite value, in contrast with what would be naively expected. The geometrical properties of these excitations are similar to those of lattice animals or branched polymers. We discuss the meaning of these results in terms of replica symmetry breaking and also possible relevance in finite dimensional systems., Comment: 7 pages, 4 figures, accepted for publication

We study the probability distribution P(E) of the ground state energy E in various Ising spin glasses. In most models, P(E) seems to become Gaussian with a variance growing as the system's volume V. Exceptions include the Sherrington-Kirkpatrick model (where the variance grows more slowly, perhaps as the square root of the volume), and mean field diluted spin glasses having +/-J couplings. We also find that the corrections to the extensive part of the disorder averaged energy grow as a power of the system size; for finite dimensional lattices, this exponent is equal, within numerical precision, to the domain-wall exponent theta_DW. We also show how a systematic expansion of theta_DW in powers of exp(-d) can be obtained for Migdal-Kadanoff lattices. Some physical arguments are given to rationalize our findings., Comment: 12 pages, RevTex, 9 figures

Using ground state computations, we study the transition from a spin glass to a ferromagnet in 3-d spin glasses when changing the mean value of the spin-spin interaction. We find good evidence for replica symmetry breaking up till the critical value where ferromagnetic ordering sets in, and no ferromagnetic spin glass phase. This phase diagram is in conflict with the droplet/scaling and mean field theories of spin glasses. We also find that the exponents of the second order ferromagnetic transition do not depend on the microscopic Hamiltonian, suggesting universality of this transition., Comment: 4 pages, 5 figures, revtex

We study the force-induced unfolding of random disordered RNA or single-stranded DNA polymers. The system undergoes a second order phase transition from a collapsed globular phase at low forces to an extensive necklace phase with a macroscopic end-to-end distance at high forces. At low temperatures, the sequence inhomogeneities modify the critical behaviour. We provide numerical evidence for the universality of the critical exponents which, by extrapolation of the scaling laws to zero force, contain useful information on the ground state (f=0) properties. This provides a good method for quantitative studies of scaling exponents characterizing the collapsed globule. In order to get rid of the blurring effect of thermal fluctuations we restrict ourselves to the groundstate at fixed external force. We analyze the statistics of rearrangements, in particular below the critical force, and point out its implications for force-extension experiments on single molecules., Comment: to be published in Europhys. J. E

We address the problem of chaotic temperature dependence in disordered glassy systems at equilibrium by following states of a random-energy random-entropy model in temperature; of particular interest are the crossings of the free-energies of these states. We find that this model exhibits strong, weak or no temperature chaos depending on the value of an exponent. This allows us to write a general criterion for temperature chaos in disordered systems, predicting the presence of temperature chaos in the Sherrington-Kirkpatrick and Edwards-Anderson spin glass models, albeit when the number of spins is large enough. The absence of chaos for smaller systems may justify why it is difficult to observe chaos with current simulations. We also illustrate our findings by studying temperature chaos in the naive mean field equations for the Edwards-Anderson spin glass., Comment: 10 pages, 5 figures; To be published in European Physics Journal B

We characterize the low temperature phase of a simple model for RNA secondary structures by determining the typical energy scale E(l) of excitations involving l bases. At zero temperature, we find a scaling law E(l) \sim l^\theta with \theta \approx 0.23, and this same scaling holds at low enough temperatures. Above a critical temperature, there is a different phase characterized by a relatively flat free energy landscape resembling that of a homopolymer with a scaling exponent \theta=1. These results strengthen the evidence in favour of the existence of a glass phase at low temperatures., Comment: 7 pages, 1 figure

We probe the energy landscape of the 3D Edwards-Anderson spin glass in a magnetic field to test for a spin glass ordering. We find that the spin glass susceptibility is anomalously large on the lattice sizes we can reach. Our data suggest that a transition from the spin glass to the paramagnetic phase takes place at B_c=0.65, though the possibility B_c=0 cannot be excluded. We also discuss the question of the nature of the putative frozen phase., Comment: RevTex, 4 pages, 4 figures, clarifications and added references

The order parameter P(q) for disordered systems with degenerate ground-states is reconsidered. We propose that entropy fluctuations lead to a trivial P(q) at zero temperature as in the non-degenerate case, even if there are zero-energy large-scale excitations (complex energy landscape). Such a situation should arise in the 3-dimensional +-J Ising spin glass and in MAX-SAT. Also, we argue that if the energy landscape is complex with a finite number of ground-state families, then replica symmetry breaking reappears at positive temperature., Comment: 7 pages; clarifications on valley definitions

We numerically extract large-scale excitations above the ground state in the 3-dimensional Edwards-Anderson spin glass with Gaussian couplings. We find that associated energies are O(1), in agreement with the mean field picture. Of further interest are the position-space properties of these excitations. First, our study of their topological properties show that the majority of the large-scale excitations are sponge-like. Second, when probing their geometrical properties, we find that the excitations coarsen when the system size is increased. We conclude that either finite size effects are very large even when the spin overlap q is close to zero, or the mean field picture of homogeneous excitations has to be modified., Comment: 11 pages, typos corrected, added references

Excitations of three-dimensional spin glasses are computed numerically. We find that one can flip a finite fraction of an LxLxL lattice with an O(1) energy cost, confirming the mean field picture of a non-trivial spin overlap distribution P(q). These low energy excitations are not domain-wall-like, rather they are topologically non-trivial and they reach out to the boundaries of the lattice. Their surface to volume ratios decrease as L increases and may asymptotically go to zero. If so, link and window overlaps between the ground state and these excited states become ``trivial''., Comment: Extra fits comparing TNT to mean field, summarized in a table