In its most elementary form, compressed sensing studies the design of decoding algorithms to recover a sufficiently sparse vector or code from a lower dimensional linear measurement vector. Typically ...it is assumed that the decoder has access to the encoder matrix, which in the combinatorial case is sparse and binary. In this paper we consider the problem of designing a decoder to recover a set of sparse codes from their linear measurements alone, that is without access to encoder matrix. To this end we study the matrix factorisation task of recovering both the encoder and sparse coding matrices from the associated linear measurement matrix. The contribution of this paper is a computationally efficient decoding algorithm, Decoder-Expander Based Factorisation, with strong performance guarantees. Under mild assumptions on the sparse coding matrix and by deploying a novel random encoder matrix, we prove that Decoder-Expander Based Factorisation recovers both the encoder and sparse coding matrix at the optimal measurement rate with high probability and from a near optimal number of measurement vectors. In addition, our experiments demonstrate the efficacy and computational efficiency of our algorithm in practice. Beyond compressed sensing, our results may be of interest for researchers working in areas as diverse as linear sketching, coding theory, matrix compression and dictionary learning.
Mahlmann and Schindelhaue (2005) proposed the following simple process, called flip-chain, for transforming any given connected d-regular graph into a d-regular expander: In each step, a random ...3-path abcd is selected, and edges ab and cd are replaced by two new edges ac and bd, provided that ac and bd do not exist already. A motivation for the study of the flip-chain arises in the design of overlay networks, where it is common practice that adjacent nodes periodically exchange random neighbors, to maintain good connectivity properties. It is known that the flip-chain converges to the uniform distribution over connected d-regular graphs, and it is conjectured that an expander graph is obtained after O(ndlogn) steps, w.h.p., where n is the number of vertices. However, the best known upper bound on the number of steps is O(n2d2√logn), and the best bound on the mixing time of the chain is O(n16d36logn).
We provide a new analysis of a natural flip-chain instantiation, which shows that starting from any connected d-regular graph, for d = Ω(log2 n), an expander is obtained after O(ndlog2n) steps, w.h.p. This result is tight within logarithmic factors, and almost matches the conjectured bound. Moreover, it justifies the use of edge flip operations in practice: for any d-regular graph with d = poly(logn), an expander is reached after each vertex participates in at most poly(logn) operations, w.h.p. Our analysis is arguably more elementary than previous approaches. It uses the novel notion of the strain of a cut, a value that depends both on the crossing edges and their adjacent edges. By keeping track of the cut strains, we form a recursive argument that bounds the time before all sets of a given size have large expansion, after all smaller sets have already attained large expansion.
Approximate Moore Graphs are good expanders Dinitz, Michael; Schapira, Michael; Shahaf, Gal
Journal of combinatorial theory. Series B,
March 2020, 2020-03-00, Volume:
141
Journal Article
Peer reviewed
Open access
We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest ...possible diameter. We focus on the reverse direction, showing that “sufficiently large” graphs of fixed diameter and degree must be “good” expanders. We prove this statement for various definitions of “sufficiently large” (multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. Aside from inherent theoretical interest, our motivation stems from the domain of network design. Both low-diameter networks and expanders are prominent approaches to designing high-performance networks in parallel computing, HPC, datacenter networking, and beyond. Our results establish that these two approaches are, in fact, inextricably intertwined. We leave the reader with many intriguing questions for future research.
We construct an infinite family of bounded-degree bipartite unique neighbour expander graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders constructed by Capalbo et ...al., our construction is simpler and may be closer to being implementable in practice, due to the smaller constants. We construct these graphs by composing bipartite Ramanujan graphs with a fixed-size gadget in a way that generalises the construction of unique neighbour expanders by Alon and Capalbo. For the analysis of our construction, we prove a strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs. Our bound generalises Kahale's average degree bound to bipartite Ramanujan graphs, and may be of independent interest. Surprisingly, our bound strongly relies on the exact Ramanujan-ness of the graph and is not known to hold for nearly-Ramanujan graphs.
A Chor–Goldreich (CG) source is a sequence of random variables X = X1 ∘ … ∘ Xt, where each Xi ∼ {0,1}d and Xi has δ d min-entropy conditioned on any fixing of X1 ∘ … ∘ Xi−1. The parameter 0<δ≤ 1 is ...the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each Xi to only have conditional Shannon entropy δ d.
We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: We construct a deterministic condenser that on input X, outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1}m for m ≈ δ dt with min-entropy m−O(1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders.
Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X1∘ … ∘ Xt, accumulate most of the entropy in X.
Efficient algorithms for approximate counting and sampling in spin systems typically apply in the so‐called high‐temperature regime, where the interaction between neighboring spins is “weak.” ...Instead, recent work of Jenssen, Keevash, and Perkins yields polynomial‐time algorithms in the low‐temperature regime on bounded‐degree (bipartite) expander graphs using polymer models and the cluster expansion. In order to speed up these algorithms (so the exponent in the run time does not depend on the degree bound) we present a Markov chain for polymer models and show that it is rapidly mixing under exponential decay of polymer weights. This yields, for example, an O(nlogn)‐time sampling algorithm for the low‐temperature ferromagnetic Potts model on bounded‐degree expander graphs. Combining our results for the hard‐core and Potts models with Markov chain comparison tools, we obtain polynomial mixing time for Glauber dynamics restricted to appropriate portions of the state space.
Expanders and box spaces Khukhro, Ana; Valette, Alain
Advances in mathematics (New York. 1965),
07/2017, Volume:
314
Journal Article
Peer reviewed
Open access
We consider box spaces of finitely generated, residually finite groups G, and try to distinguish them up to coarse equivalence. We show that, for n≥2, the group SLn(Z) has a continuum of box spaces ...which are pairwise non-coarsely equivalent expanders. Moreover, varying the integer n≥3, expanders given as box spaces of SLn(Z) are pairwise not coarsely equivalent; similarly, varying the prime p, expanders given as box spaces of SL2(Zp) are pairwise not coarsely equivalent. We also show that, for prime p, the family of finite groups (PSL2(Z/pnZ))n≥1 can be turned in infinitely many ways (up to coarse equivalence) into a 6-regular expander.
A strong form of non-expansion for a box space is the existence of α∈0,1 such that the diameter of each component Xn satisfies diam(Xn)=Ω(|Xn|α). By 2, the existence of such a box space implies that G virtually maps onto Z: we establish the converse. For the lamplighter group (Z/2Z)≀Z and for a semi-direct product Z2⋊Z, such box spaces are explicitly constructed using specific congruence subgroups.
We finally introduce the full box space of G, i.e. the metric disjoint union of all finite quotients of G. We prove that the full box space of a group mapping onto the free group F2 is not coarsely equivalent to the full box space of an S-arithmetic group satisfying the Congruence Subgroup Property.
Experiments with the Markoff Surface de Courcy-Ireland, Matthew; Lee, Seungjae
Experimental mathematics,
8/31/2022, Volume:
31, Issue:
3
Journal Article
Peer reviewed
Open access
We confirm, for the primes up to 3000, the conjecture of Bourgain-Gamburd-Sarnak and Baragar on strong approximation for the Markoff surface
modulo primes. For primes congruent to 3 modulo 4, we find ...data suggesting that some natural graphs constructed from this equation are asymptotically Ramanujan. For primes congruent to 1 modulo 4, the data suggest a weaker spectral gap. In both cases, there is close agreement with the Kesten-McKay law for the density of states for random 3-regular graphs. We also study the connectedness of other level sets
. In the degenerate case of the Cayley cubic, we give a complete description of the orbits.
PDF
