The Space of Solutions of Coupled XORSAT Formulae

Phase transitions seem indeed ubiquitous. Here is another instance of those in Boolean satisfiability problems, more specifically they appear in the random XORSAT. As shown in [1-3], XORSAT can be set as a linear algebra problem. When I read this literature, two items come to my feeble mind

• Are the thresholds observed by Baron et al (figure 2 of [4]) some sort of equivalence with the ‘Easy-SAT’ and the ‘Hard-SAT’ phases [2] observed in XORSAT ?
• When using Rvachev functions or Knolls (see discussions in [5]), one has to produce a composition of functions with Boolean results to determine the shape of things. With that in mind, I wonder if XORSAT type of problems can be fitted to the sparse shape reconstruction problem ? I also wonder if one of the real advantages of R-functions (Rvavchev function) is to provide some sort of continuation of the Boolean approach and therefore provide some sorts of relaxation thereby making the problems easier to deal with ? Can XORSAT help dictionary learning ?

Here is the paper that got me thinking about this (it uses some of the approaches used in the spatial coupling approach [6] and related seeded matrices [7] used in CS) The Space of Solutions of Coupled XORSAT Formulae by S. Hamed Hassani, Nicolas Macris, Rudiger Urbanke

The XOR-satisfiability (XORSAT) problem deals with a system of $n$ Boolean variables and $m$ clauses. Each clause is a linear Boolean equation (XOR) of a subset of the variables. A $K$-clause is a clause involving $K$ distinct variables. In the random $K$-XORSAT problem a formula is created by choosing $m$ $K$-clauses uniformly at random from the set of all possible clauses on $n$ variables. The set of solutions of a random formula exhibits various geometrical transitions as the ratio $\frac{m}{n}$ varies.

We consider a {\em coupled} $K$-XORSAT ensemble, consisting of a chain of random XORSAT models that are spatially coupled across a finite window along the chain direction. We observe that the threshold saturation phenomenon takes place for this ensemble and we characterize various properties of the space of solutions of such coupled formulae.

Of interest is this video by Andrea Montarani on the set of solutions of Random XORSAT formulae

[1] XORSAT handout by Andrea Montarani

[2] LINEAR EQUATIONS WITH BOOLEAN VARIABLES by Andrea Montarani

[3] The Set of Solutions of Random XORSAT Formulae by Morteza Ibrahimi, Yashodhan Kanoria, Matt Kraning, Andrea Montanari

[4] Performance Regions in Compressed Sensing from Noisy Measurements by Junan Zhu and Dror Baron (see also Sunday Morning Insight: Phase Transitions and Eigen-gaps as Roadmaps )

[5] SPASH: Sparse Shape Reconstruction - implementation - and Nuit Blanche Reader's Reviews: SPASH, R-Functions, Structure in Biology, Randomized Kaczmarz and SDD, AMP and GAMP.

[6] The Effect of Spatial Coupling on Compressive Sensing byShrinivas Kudekar, Henry D. Pfister.

[7] Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices by Florent Krzakala, Marc Mézard,François Sausset, Yifan Sun, Lenka Zdeborová

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.