{"id":"69683bfb-42e7-4e5c-af5b-ea98d8fdcc69","arxiv_id":"1908.01014","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":1.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A survey of compressive sensing theory and algorithms that reviews lp recovery and greedy methods and adds a limited numerical study on recovering text unigram vectors from word embeddings.","lead":"This survey organizes the main theoretical and algorithmic results in compressive sensing, from l1 and lp relaxations to greedy pursuit methods, and reports a small numerical comparison on text-embedding recovery. It is a useful map for practitioners, but it offers no new theorems, algorithms, or reproducible experiments.","discovery_kind":"review","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5's empirical claim rests on an unverified measurement model; typical unigram sparsity likely exceeds what m=50 can recover.","rationale":"The reader's weakest_assumption identifies exactly the load-bearing point: the numerical demonstration in Section 5 assumes unigram vectors are sparse enough and the embedding matrices satisfy CS conditions, without verification. My stress test agrees and sharpens it: for real documents the sparsity level is likely far too large for m=50, and GloVe columns are semantically correlated rather than incoherent, so the reported high recovery rates are not credible unless the experiment used synthetic signals or a different embedding model. This is a genuine load-bearing concern because the abstract and conclusion advertise the numerical comparison as support for the survey's practical message. However, the concern does not move the verdict: the paper is a survey, its main value is the literature overview, and the reader already issued CONDITIONAL with moderate confidence. The theorem-transcription issues and lack of reproducibility further support conditionality but do not change the overall assessment. I would keep the verdict CONDITIONAL and request the additional experimental verification as a condition of full acceptance.","tokens_in":22370,"tokens_out":3036,"duration_ms":33551,"concrete_test":"Obtain the MR and SUBJ data, form the actual unigram count vectors for the 50 documents used, and record the distribution of ||x||_0. For each m, compute the mutual coherence of the GloVe and Rademacher embedding submatrices and, if feasible, estimate the RIP constant numerically. Then rerun recovery with the true unigram vectors, the stated embedding matrices, and y = A*x_unigram, reporting success rates at the 1e-7 relative-error threshold. If real sparsity s exceeds roughly m / (C log(N/s)) at m=50 and success is still claimed, the reported experiment must have used different test signals or a different measurement model; providing code and data would settle the issue directly.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim of practical effectiveness is anchored in Section 5, which models text embeddings as Ax_unigram = y_embedding and reports successful recovery of unigram vectors from MR and SUBJ data with embedding dimensions m = 50, 100, 200, 300, 1600. For this to work, each unigram vector must be sufficiently sparse and the embedding matrix A must behave like a compressive sensing measurement matrix (low coherence or RIP). Neither condition is verified. A real document's unigram vector has one nonzero per distinct word; MR and SUBJ reviews typically contain tens to hundreds of distinct words, while m=50 supports recovery of only a handful of nonzeros under standard bounds m >= C*s*log(N/s). Moreover, GloVe columns are word vectors trained to encode semantic similarity, so they are expected to be highly coherent, not incoherent like random matrices. The paper reports no sparsity statistics, no coherence or RIP estimates, no solver details, and no numeric success rates, only figures with a 1e-7 relative-error threshold. The concluding assertion that l1 recovery and greedy algorithms are effective is therefore not supported by the experiment as described; either the test signals were modified (e.g., synthetic sparse vectors or averaged embeddings), or the stated model is invalid for real unigram vectors.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This survey reviews compressive sensing theory and algorithms, focusing on l_p recovery (including l1 and nonconvex 0<p<1) and greedy algorithms (OMP, CoSaMP, gOMP, CMP). It collects classical results such as recovery conditions based on mutual coherence, RIP, NSP, and RSP, and discusses variations including noisy measurements, nonnegative constraints, binary and quantized CS, and recent topics such as model-based CS and quantum annealing. The paper concludes with a numerical comparison of l1 recovery and greedy algorithms on unigram text representations from MR and SUBJ datasets using GloVe and Rademacher embedding matrices.","tokens_in":22600,"tokens_out":4977,"duration_ms":45862,"significance":"If the numerical section were properly substantiated, the paper would serve as a useful, compact roadmap of classical and recent compressive sensing, with a unified presentation of lp recovery and greedy algorithms. Strengths: the survey covers a broad set of results with precise theorem statements, brings together classical and recent literature (including the authors' own work on constrained matching pursuit and p>1 non-sparsity), and highlights practical issues such as determinism vs. randomness of measurement matrices. However, it introduces no new theorems or algorithms, and the empirical demonstration is central to the abstract's claim but is under-specified.","major_comments":[{"comment":"The central empirical claim is not verifiable: the figures are not present in the manuscript text (only captions appear), so the reader cannot see the success rates, and the text reports no sparsity level of the unigram vectors, no coherence or RIP estimates for the GloVe and Rademacher matrices, no algorithm implementations or parameter choices, and no standard deviations or error bars. Given that m ranges from 50 to 300 while a typical unigram vector for MR/SUBJ documents has tens to hundreds of nonzeros, the measurement model Ax_unigram = y_embedding may violate the sparsity assumptions required by the stated recovery guarantees; the claim that the results 'confirm the efficiency' is therefore unsupported as written.","section":"Section 5"},{"comment":"The model statement 'Ax_unigram^T = y_embedding^T' is dimensionally inconsistent with the earlier convention x in R^N and A in R^{m x N}: x_unigram^T is a row vector, and the use of transpose on both sides is unexplained. This makes the model ambiguous and needs correction.","section":"Section 5"},{"comment":"The constant c_A is defined as max over G with |G|=m of ||A^{-1}_G (A^T)^{-1}A||_{\\infty\\to 1}; for a rectangular m x N matrix A with m<N, (A^T)^{-1} is not defined, so the statement as written cannot be a correct quotation of [154]. Either the notation is garbled or the theorem is misquoted; the authors should check the original source and state the theorem correctly.","section":"Section 3, Theorem 3.7"},{"comment":"The claim that a sufficient condition 'delta_{3s}+27 delta_{4s}<26' follows from the displayed theorem is not self-evident; no derivation or explicit parameter substitution (p=1/2, k=?) is provided, and no citation is given for that specific condition. The authors should either derive it or cite the source.","section":"Section 3, preceding Theorem 3.8"}],"minor_comments":[{"comment":"The phrase 'its adjacent by A*' should be 'its adjoint by A^*'.","section":"Section 1, Notation"},{"comment":"The algorithm name 'CoSaPM' is a typo for 'CoSaMP' in the paragraph introducing the compressive sampling matching pursuit.","section":"Section 4"},{"comment":"'Radamacher' should be 'Rademacher'.","section":"Section 5"},{"comment":"References [107] and [108] are identical; [121] and [122] are identical; [148] and [149] are identical; these duplicates should be removed.","section":"References"},{"comment":"The sentence 'It is still an open question ... delta_{s+1} in (1/sqrt(s+1), 1/sqrt(s+1))' contains an empty interval; this is likely a typo and should be corrected.","section":"Section 4, after Theorem 4.1"}],"recommendation":"major_revision","confidential_remarks":"The survey would be strengthened by making the numerical experiment reproducible: report the sparsity of the unigram vectors, the coherence of the embedding matrices, and provide the figures with error bars. The authors' self-citations are acceptable, but the recent-advancements sections rely heavily on them; the numerical section in particular should be independently verifiable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nQuick take: this is a survey, not a research paper. No new theorems, algorithms, or data. What it does well: the organization is sensible—classical l0/l1 theory, RIP/NSP/RSP, nonconvex lp, LASSO/BPD/Dantzig, then greedy methods including OMP, CoSaMP, gOMP, block/nonnegative/constrained variants—and most of the quoted theorems are standard and correctly attributed. For a newcomer it is a passable map of the field, and the bibliography is broad. The recent-advancement section adds a few things not in the older surveys, especially constrained matching pursuit and quantum-annealing-based binary CS. Those are legitimate literature pointers, even if they come partly from the authors' own group; the citations themselves are not a problem.\n\nThe soft spot is Section 5. The authors model text embeddings as A x_unigram = y_embedding and claim l1 and greedy methods recover unigram vectors on MR and SUBJ data with m as low as 50. As reported, this doesn't hold together. Real movie-review unigram vectors have dozens to hundreds of distinct words; m=50 is far too few measurements for that sparsity under standard CS bounds. GloVe columns are also trained to encode semantic similarity, so coherence is likely high, not random-matrix small. The section gives no sparsity statistics, no coherence/RIP estimates, no solver details, no error bars, and no visible numerics in the text. The 1e-7 relative-error threshold is stated but there is no way to tell what was actually solved. Either the test signals were modified (e.g., synthetic sparse vectors or averaged embeddings) or the stated measurement model is wrong for real unigram data. Either way, the concluding empirical claim is not supported.\n\nThere are also minor transcription glitches in the theory sections—for example, the OMP open-question interval appears corrupted—but these are fixable and don't undermine the survey's main exposition. The classical recovery theorems are quoted in essentially correct form.\n\nWho is this for? A student or practitioner wanting a quick tour of CS theory and algorithms could use it, provided they don't rely on Section 5. As a peer-reviewed contribution, I would not send it to a serious referee in current form: it has no new technical content and the one piece of evidence it offers is not reproducible. If the authors replace Section 5 with a carefully specified synthetic experiment or remove it, the survey could be a reasonable arXiv-level reference. My advice: cite it if you need a compact pointer to recent constrained and quantum-annealing directions, but don't build anything on its numerical claims.","headline":"A usable but uneven compressive sensing survey; the theory sections are broadly sound, while the numerical section is too underspecified to support its claims.","tokens_in":23103,"tokens_out":3362,"would_cite":false,"duration_ms":35786,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A12","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper organizes the whole compressive sensing toolbox into two recovery strategies—$\\ell_p$ relaxation and greedy pursuit—and tests both on recovering text meanings from word embeddings.","keywords":["compressive sensing","sparse recovery","lp recovery","greedy algorithms","orthogonal matching pursuit","restricted isometry property","mutual coherence","text embeddings"],"falsifier":"Compute the mutual coherence (or estimate restricted-isometry constants) of the GloVe and Rademacher matrices actually used, with $m=50,100,200,300,1600$ and vocabularies of size 17,000 and 20,000, and measure the sparsity of the MR and SUBJ unigram vectors. If typical sparsity levels exceed the bounds of Theorem 3.1 or Theorem 4.1, or the coherence is too large, then the reported successful recoveries cannot be attributed to the compressive-sensing theory the survey presents.","tokens_in":22180,"feed_emoji":"📡","tokens_out":7740,"duration_ms":65700,"temperature":0.7,"pith_summary":"This survey maps compressive sensing through two families of recovery methods: $\\ell_p$ minimization (the convex case $p=1$ and the nonconvex case $0<p<1$) and greedy algorithms such as orthogonal matching pursuit and compressive sampling matching pursuit. It collects the classical conditions—mutual coherence, the restricted isometry property, the null space property, and the range space property—under which these methods provably recover sparse signals from linear measurements $y=Ax$. It also catalogs extensions: noisy measurement models, nonnegative and box-constrained signals, block sparsity, binary/discrete signals, 1-bit quantization, and matrix uncertainty. The survey's own experiment recovers unigram text vectors from GloVe and Rademacher embeddings of movie-review and subjectivity data, reporting that $\\ell_p$ recovery and greedy algorithms both succeed, with $\\ell_p$ winning except at very low sparsity. A fair reader would take this as a practical field guide to known guarantees and recent directions, not as a source of new theorems.","feed_headline":"From l1 relaxation to greedy pursuit: one map of compressive sensing","feed_subtitle":"It pairs classical guarantees with recent algorithms and tests them by recovering text meanings from word embeddings.","key_machinery":"The central objects are the measurement matrix $A\\in\\mathbb{R}^{m\\times N}$ and the sparsity level $s$, together with the matrix properties that certify recovery: the mutual coherence $\\mu(A)$, the restricted isometry constants $\\delta_s$, and the null space and range space properties. These properties are what let a convex relaxation or a greedy algorithm succeed despite the underlying problem being NP-hard. The algorithmic machinery is the pair of recovery families: $\\ell_p$ minimization (basis pursuit, QCBP, LASSO, BPD, Dantzig selector, iterative reweighted $\\ell_p$) and greedy pursuit (OMP, block OMP, CoSaMP, gOMP, NOMP, CMP). In the numerical comparison, a word-embedding matrix plays the role of $A$, a unigram count vector is the sparse $x$, and the text embedding is the measurement $y=Ax$.","core_discovery":"The survey's central claim is that the intractable $\\ell_0$ sparse-recovery problem is best approached by two complementary strategies, and that the existing literature can be organized accordingly. The first replaces $\\ell_0$ by an $\\ell_p$ quasi-norm: $p=1$ is the convex workhorse that becomes a linear program (basis pursuit, LASSO, basis pursuit denoising, Dantzig selector), while $0<p<1$ offers less restrictive recovery conditions at the cost of nonconvexity and the need for a good initialization. The second attacks the problem directly with greedy support selection, led by orthogonal matching pursuit and its descendants—CoSaMP, generalized OMP, nonnegative OMP, constrained matching pursuit, and block variants. The survey states the sufficient conditions that make each route work, such as the null space property for $\\ell_1$ uniqueness, $\\delta_{2s}<0.4931$ for basis pursuit, $\\delta_{s+1}\\le 1/\\sqrt{s+1}$ for OMP, and $\\delta_{8s}<0.4782$ for CoSaMP, and it notes results showing $p>1$ problems almost always return full-support solutions. Its numerical demonstration treats word-embedding matrices as measurement matrices and unigram count vectors as the sparse signals, and reports successful recovery on the MR and SUBJ datasets.","pith_inferences":["The text-embedding experiment would be more decisive if it measured the actual sparsity of unigram vectors and the coherence or RIP constants of the GloVe and Rademacher matrices; without that, the success shown could come from structure beyond the stated CS conditions.","The result that $p>1$ yields full-support solutions suggests the meaningful boundary in this area is between $p=1$ and $p<1$, not between convex and nonconvex per se; future work may focus on initialization schemes that make nonconvex recovery reliable.","If unigram vectors are truly sparse in the vocabulary basis, then recovering them from embeddings is a compressed-sensing problem, and the same lens could be applied to probing what information word embeddings preserve about individual words.","A testable extension would compare these recovery methods on embeddings other than GloVe and Rademacher, such as word2vec or context-dependent embeddings, to see whether the reported recovery success is a general property of text embeddings or specific to the two matrices tested."],"forward_implications":["A practitioner can pick a recovery method from known sufficient conditions: if the matrix has low coherence or small restricted isometry constants, $\\ell_1$ minimization and OMP-family algorithms come with explicit guarantees.","Nonconvex $\\ell_p$ with $p<1$ can recover vectors that $\\ell_1$ cannot, but only if the solver finds a global or near-global minimizer; the survey notes that a least-squares start is only an empirical heuristic.","When sparsity is small, greedy algorithms are competitive and cheap; as sparsity grows, $\\ell_p$ recovery becomes the better choice, according to the survey's text-embedding experiments.","Exploiting extra structure—nonnegativity, block sparsity, discrete alphabets, or model-based priors—reduces the number of measurements needed and sharpens recovery guarantees.","Deterministic measurement matrices can outperform random ones in specific applications, even though most theoretical guarantees are proven for random Gaussian or Bernoulli matrices."],"supporting_citations":[{"why":"Supplies the mutual-coherence uncertainty bound under which basis pursuit and the $\\ell_0$ problem have the same unique sparse solution.","marker":"[52]"},{"why":"Provides the restricted-isometry bound $\\delta_{2s}<0.4931$ for exact $\\ell_1$ recovery.","marker":"[81]"},{"why":"Serves as the standard reference for null-space-property and RIP theory, including the CoSaMP convergence theorem.","marker":"[61]"},{"why":"Introduces CoSaMP, the greedy algorithm the survey presents as correcting OMP's inability to remove wrong indices.","marker":"[89]"},{"why":"Foundational OMP analysis the survey uses for exact support recovery in at most $s$ iterations.","marker":"[124]"},{"why":"Gives the nonconvex $\\ell_p$ recovery theorem with less restrictive conditions than $\\ell_1$ for compressible signals.","marker":"[105]"},{"why":"Proves that all primary $\\ell_p$ formulations with $p>1$ return full-support solutions, motivating the focus on $p\\le 1$.","marker":"[113]"},{"why":"Provides the GloVe word embeddings used as one of the two measurement matrices in the numerical comparison.","marker":"[96]"},{"why":"Supplies the MR movie-review dataset used in the sparse text-recovery experiment.","marker":"[94]"},{"why":"Supplies the SUBJ subjectivity dataset used in the sparse text-recovery experiment.","marker":"[93]"}],"fun_headline_variants":["From L1 to OMP: a guided tour of compressive sensing","Map of sparse recovery: classical results to recent algorithms","Compressive sensing survey: word embeddings test sparse recovery","Classical guarantees, fresh algorithms: one compressive sensing survey"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that word-embedding matrices behave as valid compressive-sensing measurement matrices for unigram count vectors, meaning the unigram vectors are sparse enough and the matrices have low enough coherence or restricted-isometry constants; the survey states this model but does not measure either side of it.","fun_headline_variants_meta":{"raw":{"variants":["From L1 to OMP: a guided tour of compressive sensing","Map of sparse recovery: classical results to recent algorithms","Compressive sensing survey: word embeddings test sparse recovery","Classical guarantees, fresh algorithms: one compressive sensing survey"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001034,"raw_usage":{"total_tokens":4367,"prompt_tokens":969,"completion_tokens":3398,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":585,"completion_tokens_details":{"reasoning_tokens":3331}},"tokens_in":585,"tokens_out":3398,"duration_ms":21613,"temperature":1.0,"reasoning_tokens":3331,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:25:28.696104+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the mutual coherence (or estimate restricted-isometry constants) of the GloVe and Rademacher matrices actually used, with $m=50,100,200,300,1600$ and vocabularies of size 17,000 and 20,000, and measure the sparsity of the MR and SUBJ unigram vectors. If typical sparsity levels exceed the bounds of Theorem 3.1 or Theorem 4.1, or the coherence is too large, then the reported successful recoveries cannot be attributed to the compressive-sensing theory the survey presents.","supporting_citations":[{"cited_title":"Cosamp: Iterative signal recovery from incomplete and inaccu- rate samples","cited_arxiv_id":null,"evidence_quote":"Introduces CoSaMP, the greedy algorithm the survey presents as correcting OMP's inability to remove wrong indices."},{"cited_title":"Stable sparse approximations via nonconvex optimization","cited_arxiv_id":null,"evidence_quote":"Gives the nonconvex $\\ell_p$ recovery theorem with less restrictive conditions than $\\ell_1$ for compressible signals."},{"cited_title":"Least sparsity of p-norm based optimization problems with p> 1","cited_arxiv_id":null,"evidence_quote":"Proves that all primary $\\ell_p$ formulations with $p>1$ return full-support solutions, motivating the focus on $p\\le 1$."},{"cited_title":"Glove: Global vectors for word representation","cited_arxiv_id":null,"evidence_quote":"Provides the GloVe word embeddings used as one of the two measurement matrices in the numerical comparison."},{"cited_title":"Seeing stars: Exploiting class relationships for sentiment categoriza- tion with respect to rating scales","cited_arxiv_id":null,"evidence_quote":"Supplies the MR movie-review dataset used in the sparse text-recovery experiment."},{"cited_title":"A sentimental education: Sentiment analysis using subjectivity summa- rization based on minimum cuts","cited_arxiv_id":null,"evidence_quote":"Supplies the SUBJ subjectivity dataset used in the sparse text-recovery experiment."}],"review_version":1}