pith. sign in

arxiv: 1907.07396 · v1 · pith:CEOUMEKRnew · submitted 2019-07-17 · 🧮 math.CO

Sparse recovery guarantees for block orthogonal binary matrices constructed via Generalized Euler Squares

Pradip Sasmal , Phanindra Jampana , C. S. Sastry This is my paper

Pith reviewed 2026-05-24 20:28 UTC · model grok-4.3

classification 🧮 math.CO
keywords binary matricesblock orthogonalityblock coherencesparse recoveryEuler squaresdeterministic matricesfinite fieldsblock sparse signals
0
0 comments X

The pith

Generalized Euler squares generate binary matrices with block orthogonality and low block coherence for sparse signal recovery.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs deterministic binary matrices using a generalization of Euler squares. These matrices have orthogonal blocks and small block coherence. This structure allows guaranteed recovery of block-sparse signals. The construction achieves the largest possible number of columns for given rows and supports hardware-friendly implementations. A sympathetic reader would care because deterministic matrices avoid the unpredictability of random ones while offering explicit recovery bounds.

Core claim

Binary matrices built from Generalized Euler Squares (GES) possess a block orthogonal structure with low block coherence, enabling the recovery of block sparse signals, and the column size reaches the maximum possible order for the given row size.

What carries the argument

Generalized Euler Squares (GES), which extend Euler squares via finite field theory to produce binary matrices of arbitrary row sizes with block orthogonal properties.

Load-bearing premise

The generalization of Euler squares maintains the orthogonality and low coherence properties from the finite field construction.

What would settle it

Construct a specific Generalized Euler Square matrix for small parameters and compute its block coherence; if it exceeds the bound needed for recovery, the claim fails.

read the original abstract

In recent times, the construction of deterministic matrices has gained popularity as an alternative of random matrices as they provide guarantees for recovery of sparse signals. In particular, the construction of binary matrices has attained significance due to their potential for hardware-friendly implementation and appealing applications. Our present work aims at constructing incoherent binary matrices consisting of orthogonal blocks with small block coherence. We show that the binary matrices constructed from Euler squares exhibit block orthogonality and possess low block coherence. With a goal of obtaining better aspect ratios, the present work generalizes the notion of Euler Squares and obtains a new class of deterministic binary matrices of more general size. For realizing the stated objectives, to begin with, the paper revisits the connection of finite field theory to Euler Squares and their construction. Using the stated connection, the work proposes Generalized Euler Squares (GES) and then presents a construction procedure. Binary matrices with low coherence and general row-sizes are obtained, whose column size is in the maximum possible order. Finally, the paper shows that the special structure possessed by GES is helpful in resulting in block orthogonal structure with small block coherence, which supports the recovery of block sparse signals.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript constructs binary matrices from Generalized Euler Squares (GES) obtained by extending the finite-field construction of classical Euler squares to arbitrary row sizes. It claims that the resulting matrices possess block orthogonality and low block coherence, which in turn yields recovery guarantees for block-sparse signals via standard block-coherence bounds, while achieving column dimension of the maximum possible order.

Significance. If the generalization step preserves block orthogonality and the stated coherence bound, the work supplies an explicit deterministic family of binary matrices with structured incoherence that is directly applicable to block-sparse compressed sensing. The explicit algebraic construction and the achievement of optimal column order would constitute a concrete advance over random-matrix or purely combinatorial constructions that lack such guarantees.

major comments (3)
  1. [§3] §3 (Construction of GES): The extension from finite-field Euler squares to arbitrary row sizes is presented as a direct procedure, yet the algebraic identity that enforces block orthogonality in the prime-power case is not shown to survive the generalization; without an explicit verification that the inner-product condition between distinct blocks remains zero, the subsequent coherence claim rests on an unproven step.
  2. [§4] §4 (Block-coherence bound): The paper asserts that the block coherence is bounded by a quantity small enough to guarantee recovery, but the derivation is not supplied in full; in particular, it is unclear whether the bound remains independent of the extra parameters introduced by the generalization or whether it degrades when the row dimension is not a prime power.
  3. [Theorem 5.2] Theorem 5.2 (Recovery guarantee): The recovery theorem invokes the standard block-coherence condition, but the numerical value of the coherence achieved by the GES construction is not computed explicitly for any non-prime-power example; therefore it is impossible to confirm that the claimed column size actually satisfies the hypothesis of the theorem.
minor comments (2)
  1. [Abstract] The abstract and introduction use the phrase “maximum possible order” without a precise definition or citation to the relevant combinatorial bound; a short sentence clarifying the reference would improve readability.
  2. [§2] Notation for block size and the number of blocks is introduced inconsistently between §2 and §4; a single table summarizing the parameters would eliminate ambiguity.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments. We address each major point below and will revise the manuscript to incorporate explicit verifications, derivations, and examples as needed.

read point-by-point responses

  1. Referee: [§3] §3 (Construction of GES): The extension from finite-field Euler squares to arbitrary row sizes is presented as a direct procedure, yet the algebraic identity that enforces block orthogonality in the prime-power case is not shown to survive the generalization; without an explicit verification that the inner-product condition between distinct blocks remains zero, the subsequent coherence claim rests on an unproven step.

    Authors: We acknowledge that the manuscript describes the generalization procedure but does not include an explicit verification that the inner-product condition is preserved. In the revised version we will add a detailed proof (in §3 or an appendix) extending the algebraic identities from the prime-power case to show that the inner products between distinct blocks remain zero for arbitrary row sizes. revision: yes

  2. Referee: [§4] §4 (Block-coherence bound): The paper asserts that the block coherence is bounded by a quantity small enough to guarantee recovery, but the derivation is not supplied in full; in particular, it is unclear whether the bound remains independent of the extra parameters introduced by the generalization or whether it degrades when the row dimension is not a prime power.

    Authors: We agree the full derivation is needed. The revised manuscript will expand §4 with the complete step-by-step derivation of the block-coherence bound, explicitly demonstrating that the bound is independent of the generalization parameters and does not degrade for non-prime-power row dimensions. revision: yes

  3. Referee: [Theorem 5.2] Theorem 5.2 (Recovery guarantee): The recovery theorem invokes the standard block-coherence condition, but the numerical value of the coherence achieved by the GES construction is not computed explicitly for any non-prime-power example; therefore it is impossible to confirm that the claimed column size actually satisfies the hypothesis of the theorem.

    Authors: We agree that an explicit numerical check would strengthen the result. In the revision we will add a concrete non-prime-power example, compute the achieved block-coherence value, and verify that the column size satisfies the hypothesis of Theorem 5.2. revision: yes

Circularity Check

0 steps flagged

No circularity: direct algebraic construction from finite fields with independent coherence derivation

full rationale

The paper revisits the known finite-field link to classical Euler squares, proposes an explicit generalization procedure to obtain GES of arbitrary row sizes, constructs the binary matrices from that procedure, and then derives block orthogonality plus the coherence bound directly from the resulting block structure. No parameter is fitted to data and then renamed a prediction; no uniqueness theorem is imported from the authors' prior work to force the choice; the central recovery guarantee follows from the algebraic identities exhibited in the construction rather than reducing to the inputs by definition. The derivation chain is therefore self-contained against external algebraic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on the established link between finite fields and Euler squares; no free parameters or invented entities are introduced in the abstract. The generalization itself is the main addition.

axioms (1)
  • domain assumption Finite field theory provides a connection to Euler squares that extends to the generalized case while preserving block orthogonality.
    Abstract states that the paper revisits this connection to propose GES.

pith-pipeline@v0.9.0 · 5737 in / 1199 out tokens · 14660 ms · 2026-05-24T20:28:55.372342+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 2 internal anchors

  1. [1]

    Euler Squares,

    Harris F. MacNeish, “Euler Squares,” Ann. Math., vol-23, 221-22 7, 1922

    work page 1922

  2. [2]

    On the application of the properties of Galois fields to the problem of construction of Hyper- Graeco-latin squares,

    R. C. Bose, “ On the application of the properties of Galois fields to the problem of construction of Hyper- Graeco-latin squares,” Sankhya, The Indian Journal of St atistics, Vol.3, Part 4, 1938

    work page 1938

  3. [3]

    Deterministic Compre ssed Sensing Matrices: Construction via Euler Squares and Applications,

    R. R. Naidu, P. Jampana and C. S. Sastry, “Deterministic Compre ssed Sensing Matrices: Construction via Euler Squares and Applications,” in IEEE Transactions on Signal Pr ocessing, vol. 64, no. 14, pp. 3566-3575, July 15, 2016. 17

    work page 2016

  4. [4]

    Explicit constructions for compressed sensing of sp arse signals,

    P. Indyk, “Explicit constructions for compressed sensing of sp arse signals,” in Proc. ACM-SIAM Symp. Discrete Algorithms, pp. 30-33, 2008

    work page 2008

  5. [5]

    Deterministic Construction of Sparse Sensing Ma trices via Finite Geometry,

    S.Li and G. Ge, “Deterministic Construction of Sparse Sensing Ma trices via Finite Geometry,” IEEE Transactions on Signal Processing, VOL. 62, NO. 11, JUNE 1, 2014

    work page 2014

  6. [6]

    Sparse binary matrices of LDP C codes for compressed sensing,

    W. Z. Lu, K. Kpalma and J. Ronisn, “Sparse binary matrices of LDP C codes for compressed sensing,” in Data Compression Conference, Snowbird, Utah, USA, pp. 405-4 05, 2012

    work page 2012

  7. [7]

    Explicit constructions of RIP matrices and related problems,

    J. Bourgain, S. Dilworth, K. Ford, S. Konyagin and D. Kutzarova , “Explicit constructions of RIP matrices and related problems,” Duke Math. J. 159, 145-185, 2011

    work page 2011

  8. [8]

    The restricted isometry property and its implication s for compressed sensing,

    E. Candes, “The restricted isometry property and its implication s for compressed sensing,” Comptes Rendus Mathematique, Vol. 346, pp. 589-592, 2008

    work page 2008

  9. [9]

    Stable signal recovery fro m incomplete and inaccurate mea- surements,

    E. Candes, J. Romberg and T. Tao, “Stable signal recovery fro m incomplete and inaccurate mea- surements,” Comm. Pure and Appl. Math, 59, 1207-1223, 2006

    work page 2006

  10. [10]

    Deterministic constructions of compresse d sensing matrices,

    Ronald A. DeVore, “Deterministic constructions of compresse d sensing matrices,” Journal of Complex- ity, Volume 23,pp 918-925, 2007

    work page 2007

  11. [11]

    Decoding by linear programming,

    E. Candes and T. Tao, “Decoding by linear programming,” IEEE Tr ans. Inform. Theory 51, 42-4215, 2005

    work page 2005

  12. [12]

    A Simple Pr oof of the Restricted Isometry Property for Random Matrices,

    R. Baraniuk, M. Davenpor, R. De Vore, and M. Wakin, “A Simple Pr oof of the Restricted Isometry Property for Random Matrices,” Constructive Approximation, 28( 3),253-263, 2008

    work page 2008

  13. [13]

    From sparse solut ions of systems of equations to sparse modeling of signals and images,

    A. M. Bruckstein, D. L. Donoho and M. Elad, “From sparse solut ions of systems of equations to sparse modeling of signals and images,” SIAM Review, Vol. 51, No. 1, pp: 34-81 , 2009

    work page 2009

  14. [14]

    A remark on compressed sensin g,

    B.S. Kashin and V.N. Temlyakov, “A remark on compressed sensin g,” Matematicheskie Zametki, Vol. 82, No. 6, pp. 829837, 2007

    work page 2007

  15. [15]

    Computational methods for spa rse solution of linear inverse problems,

    J. A. Tropp and S. J. Wright, “Computational methods for spa rse solution of linear inverse problems,” Proceedings of the IEEE, vol. 98, no. 6, pp.948958, 2010

    work page 2010

  16. [16]

    An introduction to Compressive samp ling,

    E. Candes and M.B. Wakin, “An introduction to Compressive samp ling,” Signal Processing Magazine, pp:21-30, March 2008

    work page 2008

  17. [17]

    Widths of certain finite-dimensional sets and class es of smooth functions,

    B.S. Kashin, “Widths of certain finite-dimensional sets and class es of smooth functions,” Izv. Akad. Nauk SSSR, Ser.Mat. 41 (1977), 334 351; English transl. in Math. US SR IZV. 11, 317-333, 1978

    work page 1977

  18. [18]

    Deterministic construction of compressed sensing matrices via algebraic curves,

    S. Li, F. Gao, G. Ge, and S. Zhang, “Deterministic construction of compressed sensing matrices via algebraic curves,” IEEE Trans. Inf. Theory, vol. 58, 5035-5041, 2012

    work page 2012

  19. [19]

    Deterministic construction of binary , bipolar and ternary compressed sensing matrices,

    A. Amini and F. Marvasti, “Deterministic construction of binary , bipolar and ternary compressed sensing matrices,” IEEE Trans. Inf. Theory, vol. 57, 2360-2370, 2011

    work page 2011

  20. [20]

    Sparse recovery using sparsematric es,

    A. Gilbert and P. Indyk, “Sparse recovery using sparsematric es,” Proc. IEEE, vol. 98, no. 6, pp. 937-947, 2010

    work page 2010

  21. [21]

    Breaking the coherence barrier: A new theory for compressed sensing

    B. Adcock, A. Hansen, C. Poon and B. Roman, “Breaking the co herence barrier: A new theory for compressed sensing” arXiv:1302.0561v3, 2013

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  22. [22]

    An asymptotic existence result on compressed sensing matrices

    D. Bryant and P. Cathain, “An asymptotic existence result on c ompressed sensing matrices” ,arXiv:1403.2807v1, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  23. [23]

    Steiner equiangular tig ht frames

    M. Fickus, D. G. Mixon and J. C. Tremain, “Steiner equiangular tig ht frames”, Linear Algebra Appl., 436(5):10141027, 2012

    work page 2012

  24. [24]

    LDPC codes for compressed sensing,

    A. G. Dimakis, R. Smarandache, and P. O. Vontobel,“LDPC codes for compressed sensing,” IEEE Trans. Inf. Theory, vol. 58, no. 5, pp. 3093-3114, May 2012

    work page 2012

  25. [25]

    Block-Sparse Signals : Uncertainty Relations and Efficient Recovery,

    Y. C. Eldar, P. Kuppinger and H. Bolcskei, “Block-Sparse Signals : Uncertainty Relations and Efficient Recovery,” in IEEE Transactions on Signal Processing, vol. 58, no. 6, pp. 3042-3054, June 2010

    work page 2010

  26. [26]

    F-Square and Orthogonal F-Squa res Design: A Generalization of Latin Square and Orthogonal Latin Squares Design,

    A. Hedayat and E. Seiden, “F-Square and Orthogonal F-Squa res Design: A Generalization of Latin Square and Orthogonal Latin Squares Design,” The Annals of Mathe matical Statistics Vol. 41, No. 6, pp. 2035-2044, Dec., 1970

    work page 2035

  27. [27]

    Generalized latin squar es I ’

    X. Shen, Y.Z.Cai, C.L.Liu, and C. P.Kruskal, “Generalized latin squar es I ’” Discrete Applied Mathe- matics, Volume 25, Issues 12, Pp. 155-178, October 1989. 18

    work page 1989