{"id":"10159890-4a99-4d52-a9fe-d75024439b11","arxiv_id":"2501.15094","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"An eigenspace iteration factors an orthogonal matrix into a minimal product of Householder reflections, and the paper asserts that two binary-coded samples identify a Householder dictionary.","lead":"This paper studies two questions about dictionaries built from Householder reflections: how well a product of a few such reflections can approximate any orthogonal matrix, and how many data columns are needed to recover the underlying reflection from data. The authors give an eigenspace-based algorithm with error bounds for the first question, and claim two columns suffice when coefficients are binary for the second.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3 is false as stated: if the two binary columns are orthogonal to u, then Y=X and infinitely many Householder dictionaries fit, so 2 samples do not ensure unique recovery.","rationale":"The paper's headline contribution in Section 3 is the claim that two binary data columns always determine a Householder dictionary and its coefficient matrix. The proof's own text admits a division-by-zero assumption in Lemma 4, which is exactly the condition that the support sums δ1 and δ2 are nonzero. The provided counterexample shows that this condition is not merely technical: with u=(1/√2,-1/√2,0,0) and columns (1,1,0,0) and (0,0,1,1), both columns lie in the +1 eigenspace of H, so the data equal X. Any Householder reflection whose vector is orthogonal to both columns reproduces the same data, giving infinitely many dictionaries for the same observation. This is not a boundary case requiring special limiting arguments; it is a simple, explicit instance satisfying the theorem's stated hypotheses. Consequently, Theorem 3 is false as stated, and the advertised two-sample identifiability result does not hold. The Section 2 approximation algorithm and its error bounds appear to be a separate contribution, and this stress-test does not target them. Because the reader's weakest assumption identified the same division-by-zero gap and the same counterexample, I agree with the REJECT verdict; no adjustment is needed.","tokens_in":15339,"tokens_out":6147,"duration_ms":57369,"concrete_test":"Run Algorithm 2 or direct algebra on the n=4 instance Y=X, where X has columns (1,1,0,0)^T and (0,0,1,1)^T and the true dictionary is H0=I-2u0u0^T with u0=(1/√2,-1/√2,0,0). Verify that H0X=Y and then test a second unit vector v=(0,0,1/√2,-1/√2), which also satisfies v1+v2=0 and v3+v4=0, and check that (I-2vv^T)X=Y. If it does, uniqueness is disproved immediately; this is four lines of arithmetic or a five-line script.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3 (Section 3.2, Lemma 4) says 'We assume that we do not divide by 0 in any case,' but this nondegeneracy condition is not carried into the theorem statement. When it fails, the central identifiability claim is false. Let n=4, u=(1/√2, -1/√2, 0, 0), and H0=I-2uu^T, which swaps the first two coordinates and fixes the last two. Take the distinct binary columns x1=(1,1,0,0)^T and x2=(0,0,1,1)^T. Both columns are orthogonal to u, so H0x1=x1 and H0x2=x2, giving Y=X. For every unit vector v in the two-dimensional subspace {v1+v2=0, v3+v4=0}, the Householder matrix Hv=I-2vv^T also fixes both columns, so HvX=Y. Thus there is a continuum of valid Householder dictionaries agreeing with Y and X, and unique recovery of (H,X) fails even with two distinct, nonzero, binary columns. The theorem would need an explicit nondegeneracy condition such as nonzero support sums δ1 and δ2; as written, it is false. A secondary gap is that Lemma 5(1), |P2|=|P4|, does not imply the later claim that 'the two matrices are only different due to permutation,' but the counterexample already refutes the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two problems. The first is approximation of a real orthogonal matrix by a product of a small number of Householder reflections. The authors propose an eigenspace-based greedy algorithm (Algorithm 1), prove that it terminates exactly when the input lies in H_m (Theorem 1), and give a Frobenius-norm error bound for arbitrary inputs (Theorem 2). The second problem is identifiability in the structured dictionary-learning model Y = HX, where H is an unknown Householder matrix and X is an unknown binary coefficient matrix. Theorem 3 claims that two columns of Y suffice to recover (H,X) uniquely, and Theorem 4 claims that without the binary restriction recovery is impossible. The paper also contains simulations for the approximation algorithm and a small illustrative table for the two-sample claim.","tokens_in":15666,"tokens_out":9193,"duration_ms":86797,"significance":"If Theorem 3 were correct, it would be a striking result: only two samples would be needed to identify a Householder dictionary from binary coefficients, much smaller than the sample sizes required in prior dictionary-learning work. The approximation algorithm and its error bound are of moderate interest, and the explicit non-uniqueness construction for arbitrary X (Theorem 4) is a useful sanity check. However, Theorem 3 is false as stated, and the proof contains a non-rigorous key step. Since the two-sample identifiability claim is the paper's main advertised contribution, the current version cannot be accepted. The first part of the paper might be salvageable separately, but the central claim of Section 3 is invalid.","major_comments":[{"comment":"Theorem 3 is false as stated. Let n=4, u=(1/sqrt(2), -1/sqrt(2), 0, 0), H=I-2uu^T, and let the binary coefficient matrix be X=[x1 x2] with x1=(1,1,0,0)^T and x2=(0,0,1,1)^T. Since u^T x1 = u^T x2 = 0, we have HX=X, so Y=X. For every unit vector v in the two-dimensional subspace {v in R^4 : v1+v2=0, v3+v4=0}, the Householder matrix H_v=I-2vv^T also fixes x1 and x2, hence H_v X = Y. This is a continuum of distinct Householder dictionaries producing the same data, so (H,X) is not uniquely recoverable from two distinct binary columns. In the proof of Lemma 4 the sentence \"We assume that we do not divide by 0 in any case\" hides the assumptions delta1 != 0 and delta2 != 0, which fail in this example (delta1=delta2=0). These nondegeneracy assumptions are absent from the theorem statement, so the theorem and the abstract's claim that two samples suffice are false.","section":"Section 3.2, Theorem 3 and Lemma 4"},{"comment":"The conclusion \"According to result 1 in Lemma 5, the two matrices are only different due to permutation\" is not justified. Lemma 5(1) states only |P2|=|P4|, an equality of cardinalities of two index sets; it says nothing about the coefficient matrices or Householder vectors being permutations of one another. This non sequitur is used as a step toward uniqueness. Even apart from the division-by-zero issue, the proof of uniqueness for the second column relies on informal assertions such as \"there is a one-to-one relationship\" and does not constitute a rigorous derivation. Thus the proof of Theorem 3 is incomplete in multiple places.","section":"Section 3.2, Lemma 5 and following paragraph"}],"minor_comments":[{"comment":"The text \"we find matrcies H3, H4\" contains a typo; the surrounding algebra is dense and would benefit from a cleaner derivation or a reference to a supplementary computation.","section":"Section 2.5"},{"comment":"The phrase \"Here delta_ik is the standard indicator for j = k\" should read \"for i = k\"; the Kronecker delta in the formula compares row indices i and k.","section":"Equation (3)"},{"comment":"Algorithm 2 is not a fully specified deterministic algorithm: it says \"Set the first column of X as a random n length binary vector\" and \"Find u\" without characterizing the solution set for a given guess or giving a formal termination condition. The exponential complexity is acknowledged, but the correctness statement is a direct consequence of the (false) Theorem 3 and therefore cannot be accepted.","section":"Algorithm 2"},{"comment":"The remark that binary constraints \"ensure that up to permutation, only O(n) such possibilities existed\" is inaccurate: there are 2^n binary vectors of length n, not O(n). This does not affect the example itself, but the motivating statement should be corrected.","section":"Proof of Theorem 4"},{"comment":"The conclusion that \"meaningful lower bounds on sample complexity ... can only be obtained by restricting the dictionary learning algorithm to be polynomial time\" is not supported by the preceding theorems, which concern information-theoretic identifiability rather than algorithmic lower bounds; the discussion should be clarified.","section":"Section 4"},{"comment":"There are numerous typos and formatting issues: \"consoderation\", \"his will hopefully\", missing spaces in the product notation, and garbled table entries in the Section 3.3 illustration. A careful editorial pass is needed before resubmission.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The central contribution of the paper, Theorem 3, is false as stated; the counterexample in the report is not a borderline or measure-zero pathology within the theorem's stated assumptions. The proof's division-by-zero assumption and the non sequitur around Lemma 5(1) indicate that a correct generic version of the theorem would require substantial new work, not a local patch. The approximation part of the paper may be salvageable as a separate contribution, but the current submission's main advertised result does not hold. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two contributions, one good, one broken. The eigenspace-based algorithm for factoring an orthogonal matrix into a product of m Householder matrices, with the smallest-m guarantee and the truncation error bound (Theorems 1 and 2), is a plausible and useful variant of the known construction in [16]. The error bound in terms of the eigenvalues of the symmetric part is new as far as I know, and the numerical experiments support the claim. I did not find an obvious gap in that half.\n\nThe second half, however, is not correct. Theorem 3 claims that two columns of Y = HX with binary X always determine H and X uniquely. The proof only works under an unstated assumption that you never divide by zero; the line \"We assume that we do not divide by 0 in any case\" appears in the proof of Lemma 4, but the theorem statement does not carry any such condition. When the assumption fails, the claim is simply false. Take n=4, u=(1/sqrt(2), -1/sqrt(2), 0, 0), and the two distinct binary columns x1=(1,1,0,0)^T and x2=(0,0,1,1)^T. Both columns are orthogonal to u, so H = I - 2uu^T fixes them, Y = X. For any unit vector v in the two-dimensional subspace {v1+v2=0, v3+v4=0}, the Householder matrix I - 2vv^T also fixes both columns, so infinitely many distinct Householder dictionaries give exactly the same Y. There is also a gap in the proof after Lemma 5: the equality |P2| = |P4| does not imply that the two solutions differ only by permutation. That step is asserted, not derived.\n\nThe non-uniqueness result for arbitrary X (Theorem 4) is true but unsurprising; it does not compensate. The discussion's concluding remark about polynomial-time restrictions is sensible but underdeveloped.\n\nNet: the advertised sample-complexity result is load-bearing and false. The approximation half may be salvageable as a standalone contribution, and a corrected identifiability theorem with explicit nondegeneracy assumptions might be recoverable. As written, I would not accept the paper. I would still send it to peer review rather than desk-reject, because the approximation algorithm is a real, defensible contribution and the counterexample should be put on record. With a major revision focused on the dictionary-learning section, this could become a useful paper.","headline":"The approximation half is a real contribution; the two-sample identifiability theorem is false as stated, so the paper needs major surgery.","tokens_in":16174,"tokens_out":3776,"would_cite":false,"duration_ms":33284,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A23","15A18","65F25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper shows that two binary-coded columns of $Y=HX$ uniquely determine a Householder reflection matrix $H$ and the coefficient matrix $X$.","keywords":["Householder reflections","structured dictionary learning","orthogonal matrix factorization","sample complexity","binary coefficient matrix","fast transforms","dictionary recovery","eigendecomposition"],"falsifier":"Take $u=(1/\\sqrt{2},-1/\\sqrt{2},0,0)$ with binary columns $x_1=(1,1,0,0)^T$ and $x_2=(0,0,1,1)^T$; then $H=I-2uu^T$ fixes both columns, so $Y=X$, and any other Householder reflection whose vector is orthogonal to the two columns also fixes them, contradicting the unqualified two-column uniqueness claim unless the zero-support-sum condition is added.","tokens_in":15112,"feed_emoji":"🧮","tokens_out":11041,"duration_ms":89362,"temperature":0.7,"pith_summary":"This paper addresses two questions about dictionaries built from Householder reflections, matrices of the form $H = I - 2uu^T$ with $u$ a unit vector. For approximation, it gives an algorithm that, given an orthogonal matrix $V$ and a target number $m$ of reflections, returns a product of $m$ Householders whenever $V$ is exactly such a product, finds the smallest such $m$, and, when truncated, comes with an explicit Frobenius-norm error bound. For learning, it claims that if observed data obey $Y = HX$ with $H$ a single Householder matrix and $X$ a binary ($0/1$) coefficient matrix, then two columns of $Y$ determine both $H$ and $X$ uniquely. This matters because storing and applying a product of $m$ Householders costs $O(mn)$ rather than $O(n^2)$, and two-column identifiability is far below what classical dictionary learning requires. The paper also proves the binary assumption is load-bearing: without it, no finite number of columns makes the recovery unique.","feed_headline":"Two binary-coded columns fix a Householder dictionary","feed_subtitle":"When X is 0/1, two columns of Y=HX identify the reflection and its coefficients; without that, no sample count works.","key_machinery":"The central objects are Householder reflections $H = I - 2uu^T$ for unit vectors $u$, and their symmetric parts. For approximation, the carrier of the argument is the eigenspace $E^1_V$ of eigenvalue $1$: a product of $m$ Householders has an eigenvalue-$1$ eigenspace of dimension at least $n-m$, and Algorithm 1 chooses $u$ as the eigenvector of the smallest eigenvalue of $(V_k + V_k^T)/2$, forms $H_k = I - 2uu^T$, and updates $V_{k+1} = H_k V_k$. Lemma 3 is the key mechanism: each iteration raises the dimension of the eigenvalue-$1$ eigenspace by exactly one, forcing termination at the minimal factor count. For the dictionary-learning theorem, the load-bearing structure is the binary support pattern of a column of $X$. The proof partitions rows into four sets $P_1,\\ldots,P_4$ according to which of two candidate solutions have zero coefficients, introduces $\\delta_1$ and $\\delta_2$ as the sums of the candidate Householder vectors over zero-support positions, and Lemma 4 expresses one candidate vector entrywise as an affine function of the other; Lemma 5 then derives $|P_2| = |P_4|$, $\\delta_2/\\delta_1 = c_1/c_2$, and ratio identities that leave no room for a second consistent vector when two distinct binary columns are used.","core_discovery":"On the approximation side, the paper's central claim is that membership in $\\mathcal{H}_m$ — the set of orthogonal matrices expressible as a product of at most $m$ Householder reflections — can be tested by repeatedly peeling off the reflection whose vector is the unit eigenvector of the smallest eigenvalue of the current residual's symmetric part $(V+V^T)/2$. Algorithm 1 performs this peeling; Theorem 1 states that it terminates at exactly the minimal $m$ with $V \\in \\mathcal{H}_m$, and Theorem 2 gives the error bound $\\|V - \\hat{V}_m\\|_F \\leq \\sqrt{2(n - \\operatorname{tr}(V) - 2\\lfloor m/2 \\rfloor + \\sum_{i=1}^m \\lambda_i)}$, with $\\lambda_i$ the sorted eigenvalues of $V_{\\mathrm{sym}}$. On the learning side, the paper's central claim is Theorem 3: for $Y = HX$ with $H = I - 2uu^T$ and $X$ an arbitrary binary matrix, two columns in $Y$ uniquely recover $H$ and $X$. The proof enumerates the $2^n$ binary vectors for the first column, solves the $n$ linear equations $Y_{ij} = \\sum_k (\\delta_{ik} - 2u_i u_k)X_{kj}$ for $u$, and shows through Lemmas 4 and 5 that two distinct columns cannot both admit the same spurious reflection vector unless the columns are identical, so only the true $u$ survives. Theorem 4 complements this by exhibiting two genuinely different real non-binary pairs $(H,X)$ with the same product, so the binary restriction is what makes two-sample recovery possible.","pith_inferences":["The proof as written divides by $\\delta_1$ and $\\delta_2$ but the theorem statement does not state the nonzero-support-sum condition; counterexamples such as $u=(1/\\sqrt{2},-1/\\sqrt{2},0,0)$ with columns $(1,1,0,0)$ and $(0,0,1,1)$ suggest the statement needs that hypothesis made explicit.","Because arbitrary real coefficients defeat recovery even with unlimited samples, the discrete-versus-continuous gap suggests that identifiability of orthogonal dictionaries is governed by the coefficient model at least as much as by sample count.","The eigenvector-peeling strategy may extend to the generalized reflectors $z_1 I - z_2 uu^T$ floated in the discussion, where a richer class of orthogonal matrices could be approximated with fewer building blocks; testing this would require re-deriving the one-dimensional eigenspace growth step.","A natural next question is whether any polynomial-time algorithm can achieve the two-sample bound; the paper's exponential enumeration suggests a lower bound for efficient algorithms may exist, and proving one would sharpen the sample-complexity picture."],"forward_implications":["An orthogonal matrix known to be a product of $m$ Householders can be certified and factored in $O(n^3 m)$ time, yielding $O(mn)$ storage and $O(mn)$ per matrix-vector product instead of $O(n^2)$.","Truncating Algorithm 1 at $m$ steps gives a guaranteed approximation bound in terms of the spectrum of $V_{\\mathrm{sym}}$, so the same procedure doubles as a fast-transforms approximation scheme.","For structured dictionary learning with binary coefficients, two distinct data columns are information-theoretically sufficient, so the sample complexity is exactly $2$ rather than growing with $n$.","Without a binary or similarly discrete coefficient constraint, the dictionary recovery problem is unidentifiable no matter how many samples are provided, so any polynomial-time method must exploit additional structure.","The constructive proof enumerates binary vectors and is exponential-time, so the two-sample guarantee does not promise a polynomial-time algorithm; the paper notes that meaningful lower bounds for efficient algorithms remain open."],"supporting_citations":[{"why":"Supplies the constructive fact that every real orthogonal matrix is a product of n Householder matrices and the eigenspace sufficiency condition used in Theorem 1.","marker":"[16]"},{"why":"Earlier paper by the same authors bounding the number of data columns needed to recover a Householder dictionary under a statistical coefficient model; the binary-X result refines it to two columns.","marker":"[15]"},{"why":"Introduces fast orthonormal sparsifying transforms built from Householder reflections, the structured-dictionary setting this paper studies.","marker":"[13]"},{"why":"Classical Householder QR, whose column-wise construction generally returns n factors even for a matrix in H_1; this contrast motivates Algorithm 1's eigenspace approach.","marker":"[17]"}],"fun_headline_variants":["Householder dictionary from just two samples","Binary X: two columns recover H and X","Exact Householder decomposition with error bound","Two samples enough for binary dictionary learning","Peel reflections, bound the approximation error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The uniqueness proof for the two-column recovery divides by $\\delta_1$ and $\\delta_2$, the sums of the true Householder vector entries over the zero positions of the two binary columns, so it assumes both support sums are nonzero and that the two columns are distinct; if a column's zero-support sum vanishes, the same data can be consistent with many different Householder dictionaries.","fun_headline_variants_meta":{"raw":{"variants":["Householder dictionary from just two samples","Binary X: two columns recover H and X","Exact Householder decomposition with error bound","Two samples enough for binary dictionary learning","Peel reflections, bound the approximation error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000374,"raw_usage":{"total_tokens":2063,"prompt_tokens":1078,"completion_tokens":985,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":920}},"tokens_in":694,"tokens_out":985,"duration_ms":9859,"temperature":1.0,"reasoning_tokens":920,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:39:25.471160+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $u=(1/\\sqrt{2},-1/\\sqrt{2},0,0)$ with binary columns $x_1=(1,1,0,0)^T$ and $x_2=(0,0,1,1)^T$; then $H=I-2uu^T$ fixes both columns, so $Y=X$, and any other Householder reflection whose vector is orthogonal to the two columns also fixes them, contradicting the unqualified two-column uniqueness claim unless the zero-support-sum condition is added.","supporting_citations":[{"cited_title":"Constructive ways for generating (generalized) real orthogonal matrices as products of (gen- eralized) symmetries,","cited_arxiv_id":null,"evidence_quote":"Supplies the constructive fact that every real orthogonal matrix is a product of n Householder matrices and the eigenspace sufficiency condition used in Theorem 1."},{"cited_title":"Fast Structured Orthogonal Dictionary Learning using Householder Reflections","cited_arxiv_id":"2409.09138","evidence_quote":"Earlier paper by the same authors bounding the number of data columns needed to recover a Householder dictionary under a statistical coefficient model; the binary-X result refines it to two columns."},{"cited_title":"Fast orthonormal sparsifying transforms based on householder reflectors,","cited_arxiv_id":null,"evidence_quote":"Introduces fast orthonormal sparsifying transforms built from Householder reflections, the structured-dictionary setting this paper studies."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Classical Householder QR, whose column-wise construction generally returns n factors even for a matrix in H_1; this contrast motivates Algorithm 1's eigenspace approach."}],"review_version":1}