{"id":"17526775-e5e9-4162-8c58-db7868de38b2","arxiv_id":"2502.07782","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"The Flag Decomposition factors a matrix with a nested column hierarchy into an orthonormal flag, a block upper triangular matrix, and a permutation, computed by a block Gram-Schmidt algorithm.","lead":"This paper introduces the Flag Decomposition, a matrix factorization that preserves user-specified nested column structures while producing low-rank approximations. It may interest engineers working with spectral or hierarchical data because it offers a hierarchy-aware alternative to SVD and QR.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Prop. 3 is only established for the full-rank flag type n_i = rank(D_Ai); all experiments use truncated types, so the claimed hierarchy-preserving FD does not actually apply to them.","rationale":"The algebraic construction behind Prop. 3 is sound as an exact factorization at the rank-determined flag type: given a column hierarchy, block orthogonalization yields Q, R, P with D = QRP^T and exact subspace equalities. My concern is not a counterexample to that construction, but a scope mismatch between the theorem and the way the paper uses it. The theorem is stated for a generic flag type (n1,...,nk;n), while its proof only covers n_i = rank(D_Ai). All experiments choose truncated types (e.g., n_k < rank(D̃)), so the exact equality [D_Ai]=[Q1,...,Qi] cannot hold and the hierarchy-preserving guarantee is void. The paper acknowledges that the output is a reduced-rank approximation, but it does not provide any approximation-theoretic statement: no bound on the reconstruction error, no characterization of the optimal truncated flag, and no analysis of whether the column hierarchy is approximately preserved. This matters because the applications are the main evidence of utility, and the reader's conditional verdict already asks for sensitivity analysis. My proposed check would settle whether the experimental configurations violate the exactness condition; if they do, the paper should either restrict the claim to full-rank types or develop and state the truncated/approximate theory. This does not require changing the verdict: 'conditional' already captures the need for scope clarification. I partially agree with the reader's weakest-assumption identification because the strict rank condition is a special case of the type/rank mismatch, but the broader issue is that even valid hierarchies with truncated flag types fall outside the theorem.","tokens_in":23927,"tokens_out":23339,"duration_ms":205871,"concrete_test":"On the few-shot features, for each class and each s, compute r1 = rank(D_A1) and r2 = rank(D_A2) for the AlexNet feature blocks, and also measure the subspace errors ||D_Ai − Q_{:i}Q_{:i}^T D_Ai||_F / ||D_Ai||_F after running Flag-BMGS with the paper's type (s−1,2(s−1)). If r1 > s−1 or r2 > 2(s−1) for a substantial fraction of classes, or if the subspace errors are non-negligible, then the empirical pipelines are operating in the truncated regime where Prop. 3 does not apply and the output is not an exact hierarchy-preserving FD. The same check should be run on the hyperspectral denoising setup with the (8,9,10;2500) flag type.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Prop. 3 (Prop. 7 in the appendix) states that D admits a flag decomposition of type (n1,...,nk;n) iff A1⊂...⊂Ak is a column hierarchy. As written, this is too strong: the proof constructs Q with n_i = rank(D_Ai) (Prop. 1), and the equality [D_Ai] = [Q1,...,Qi] in Def. 5 forces dim[D_Ai] = n_i. If the user requests any other type, e.g. n_i < rank(D_Ai), no exact hierarchy-preserving FD exists: [Q1,...,Qi] has dimension n_i and cannot equal the higher-dimensional [D_Ai]. The paper itself recommends this truncated regime ('we choose a flag type where n_k < rank(D̃)'), and all applications use it: HSI denoising uses (8,9,10;2500) while the band blocks are far higher-rank, and few-shot uses (s−1,2(s−1)) without checking the ranks of the AlexNet feature blocks. In these cases Flag-BMGS silently returns an approximation, but the paper never states a theorem for approximate/truncated flag decompositions, never bounds the hierarchy-preservation error, and uses the exactness of Prop. 3 to justify the method. The few-shot hierarchy assumption in Example 2.3 is a second unverified instance of the same gap: even if f^(1) features lie in the span of the full features (which is not tested), the chosen flag type must also match the empirical ranks for the exact FD guarantee to hold.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Flag Decomposition (FD), a factorization D = Q R P^T in which Q is a Stiefel-coordinate representative of a flag associated with a user-specified hierarchy on the columns of D, R is block upper triangular, and P is a permutation that orders columns by hierarchy blocks. The authors prove existence for the exact flag type n_i = rank(D_{A_i}) (Props. 1-3 / 5-7), state a block-rotational ambiguity (Prop. 4/8), propose the Flag-BMGS algorithm and a robust IRLS variant to compute the decomposition, and apply the method to denoising, clustering, and few-shot learning. Experiments on simulated data, AVIRIS hyperspectral images, and ImageNet-feature few-shot benchmarks report improvements over SVD and QR baselines.","tokens_in":24243,"tokens_out":4907,"duration_ms":42864,"significance":"The exact existence result is correct, and the paper ships code, which makes the experiments reproducible. The geometric framing (Stiefel coordinates for flags, chordal distances on flag manifolds) is appropriate, and the few-shot prototype idea is original. However, the advertised 'hierarchy-preserving' claim is proved only when the flag type equals the empirical ranks of the hierarchy blocks. All applications use truncated flag types, so a central theoretical support for those results is missing. The paper is nevertheless a meaningful step, and the gap is addressable with an explicit approximation analysis or with a flag-type selection step.","major_comments":[{"comment":"As stated, Proposition 3 asserts the equivalence between existence of an FD of type (n1,...,nk;n) and A1⊂...⊂Ak being a column hierarchy. This is missing the condition n_i = rank(D_{A_i}) for all i. Definition 5 requires [D_{A_i}] = [Q_1,...,Q_i]; since Q has orthonormal columns, dim([Q_1,...,Q_i]) = n_i, so equality forces n_i = dim([D_{A_i}]). The proof of Prop. 7 itself uses this dimension matching when it derives Eq. (32). Consequently, if the user specifies any truncated type with n_i < rank(D_{A_i}) — precisely the regime recommended in Sec. 3.2 ('we choose a flag type where n_k < rank(˜D)') — no exact hierarchy-preserving FD exists. The statement should either include the rank constraint or define an approximate FD and bound how well [Q_1,...,Q_i] approximates [D_{A_i}].","section":"Sec. 3, Prop. 3 (and App. B, Prop. 7)"},{"comment":"The experimental sections use truncated flag types: HSI denoising uses (8,9,10;2500) without reporting the ranks of the band blocks, and few-shot uses (s−1,2(s−1)) for data matrices in R^{4096×2s}. In both cases the rank of D_{A_i} is almost certainly larger than n_i, so Definition 5 is violated exactly. The claim in the abstract that FD 'decomposes arbitrary hierarchical real-valued data into a hierarchy-preserving flag representation' is therefore not supported for the configurations that are actually evaluated. Please add a formal statement for the truncated case (e.g., an approximation bound in chordal distance or a guarantee on the nested subspace residuals) and verify the rank condition for the feature hierarchy in Example 2.3.","section":"Secs. 5.3 and 5.5; Sec. 3.2"},{"comment":"The feature hierarchy assumes [f^(1)_Θ(x_1),...,f^(1)_Θ(x_s)] ⊆ [f_Θ(x_1),...,f_Θ(x_s)] ('information flows from f^(1)_Θ to f^(2)_Θ'). This inclusion is not tested on the AlexNet features used in Sec. 5.5. If it fails, then A1 ⊂ A2 is not a column hierarchy for D, and even the full-rank version of Prop. 3 does not apply. The few-shot experiments should either verify this inclusion empirically or state the hierarchy as an assumption of the method.","section":"Sec. 2, Example 2.3"}],"minor_comments":[{"comment":"The caption spells 'Stiefel' as 'Steifel'; please correct the typo.","section":"Table 1"},{"comment":"The vertical axis is labeled 'LSRE' but the metric defined in Table 3 is 'LRSE'; please make the labels consistent.","section":"Fig. 6"},{"comment":"The sentence following Eq. (15) says the distance is 'proportional to the squared chordal distance on FL(1,2;n)' when the query matrix is in Stiefel coordinates. The constant of proportionality and the exact condition on the query matrix should be stated explicitly.","section":"Sec. 4.3, Eq. (15)"},{"comment":"The output line states 'D=QRP^T' without qualification. For truncated flag types the equality is only approximate; please use '≈' or include a residual term so the algorithm's output matches the theory.","section":"App. D, Algorithm 2"}],"recommendation":"major_revision","confidential_remarks":"The gap between Prop. 3 and the truncated flag types used in every experiment is the main reason for major revision. The paper's Limitations section acknowledges that a flag type and hierarchy must be supplied, but it does not flag that the existence theorem only holds for exact ranks. The few-shot gains over subspace classifiers are modest (often 1 percentage point or less, and sometimes equal), but the comparison is fair and the method introduces a new prototype geometry. I would not reject on this basis; the theoretical statement needs correction and the experiments need a rank check or an approximation analysis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is block QR with a prescribed column permutation, re-framed as a hierarchy-preserving flag decomposition, plus a robust solver and three applications. The framing is genuinely useful, the proofs are elementary but correct, and the paper ships code and experiments. The problem is that the central theorem overstates what the method guarantees, and the experimental wins are smaller than the abstract suggests.\n\nWhat is actually new: the specific D = QRP^T factorization with a flag in Stiefel coordinates, the Flag-BMGS algorithm, and the robust IRLS-SVD variant. Props. 1–3 are correct as block Gram–Schmidt on the permuted matrix; Prop. 4 on rotational ambiguity is standard. The HSI denoising and clustering experiments are honest and show small but real gains for Gaussian noise and for k-NN clustering.\n\nWhere it gets soft. The stress-test note is on target. Prop. 3 claims D admits a flag decomposition of type (n1,...,nk;n) iff the column hierarchy holds, but the proof only works when n_i = rank(D_Ai). If you choose a truncated type — as the paper explicitly recommends and as all experiments do, e.g., (8,9,10;2500) on HSI or (s−1,2(s−1)) for few-shot — no exact hierarchy-preserving FD exists. Flag-BMGS silently returns an approximation, and there is no theorem bounding the hierarchy-preservation error. This is a load-bearing gap because exactness is what motivates the method. It is fixable: state the exact result for full-rank types, then add an approximate decomposition theorem with error control for truncated types.\n\nThe few-shot results are also weaker than the text implies: the flag classifier essentially ties the subspace baseline in every setting, with differences inside the reported standard deviations. The feature hierarchy assumption in Example 2.3 (that early AlexNet features span a subspace of full features) is asserted, not tested. Denoising gains only appear for Gaussian noise; exponential and uniform noise give no improvement.\n\nThe paper is still worth refereeing. The idea is clear, the code is available, the experiments are reproducible in spirit, and the limitations section is honest about needing user-supplied hierarchies and flag types. The main fix is aligning the theory with the truncated regime actually used. I would not desk reject; a serious referee should ask for the theorem gap to be closed and the few-shot claims to be toned down.","headline":"Block QR in flag clothing with a real theorem/practice gap on truncated flag types, plus modest experimental gains.","tokens_in":24799,"tokens_out":3118,"would_cite":true,"duration_ms":29512,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A23","14M15","65F25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that any matrix with nested column groups of strictly increasing rank admits a hierarchy-preserving flag decomposition D=QRP^T, and gives an algorithm to compute it.","keywords":["flag decomposition","flag manifolds","Stiefel coordinates","hierarchical data","block Gram-Schmidt","few-shot learning","hyperspectral image denoising","subspace recovery"],"falsifier":"Compute the ranks of [D_{A_i}] for a concrete dataset with a proposed hierarchy; if any two consecutive groups have equal rank, the if-and-only-if theorem says no exact flag decomposition exists, so Flag-BMGS output cannot be hierarchy-preserving. Concretely, duplicating a column across two nested groups makes the rank increments vanish. For the few-shot claim, one can numerically check whether the span of early-layer AlexNet features is contained in the span of the full features on the actual support set; a counterexample would invalidate the flag-prototype distance.","tokens_in":23722,"feed_emoji":"🚩","tokens_out":6647,"duration_ms":57012,"temperature":0.7,"pith_summary":"This paper introduces a matrix factorization that preserves nested hierarchies in data. It proves that whenever a data matrix's columns can be partitioned into nested groups with strictly increasing ranks, the matrix admits an exact decomposition D=QRP^T, where Q is an orthonormal basis for a flag (a nested sequence of subspaces), R is block upper triangular, and P is a permutation. The authors give an algorithm, Flag-BMGS, that constructs this decomposition block by block and a robust variant for data with outlier columns. They show the decomposition improves denoising and clustering of hyperspectral images and, used as class prototypes, improves few-shot classification accuracy on several benchmarks. Standard tools like SVD and QR either ignore the hierarchy or can only recover limited nested structure, so this is a general, hierarchy-preserving alternative.","feed_headline":"Hierarchical data admit exact flag decompositions","feed_subtitle":"A new QRP^T factorization keeps nested subspaces intact and improves denoising and few-shot learning.","key_machinery":"The central object is the flag manifold F L(n1,...,nk;n) in Stiefel coordinates: a tall-skinny orthonormal matrix Q=[Q1|...|Qk] whose prefixes span a nested sequence of subspaces. The load-bearing identity is the projection property Π_{Q_i^⊥} ... Π_{Q_1^⊥} B_i = 0, which holds exactly when the nested column groups have strictly increasing rank; it lets each block B_i be reconstructed from its projections onto the flag pieces. Flag-BMGS is a block modified Gram-Schmidt procedure that builds Q block by block, solving a small subspace-recovery problem at each step, and assembles R and P from those projections. The rotational ambiguity of Stiefel coordinates (Prop. 4) means the decomposition is unique as a flag, not as a matrix.","core_discovery":"The central claim is that flag decomposition is exactly the right factorization for hierarchical data: a matrix D admits a flag decomposition of type (n1,...,nk;n) if and only if the nested column index sets A1⊂...⊂Ak form a column hierarchy, meaning dim([D_{A_{i-1}}]) < dim([D_{A_i}]) for every i. When this holds, one can construct an n×n_k matrix Q with orthonormal columns, partitioned as Q=[Q1|...|Qk], whose prefixes span exactly the same nested subspaces as the column groups of D; together with a block upper triangular R and a permutation P, it satisfies D=QRP^T. The construction is explicit: project each block onto the orthogonal complement of all previous flag pieces, take an orthonormal basis of the result (via SVD, or IRLS-SVD for robustness), and assemble R from the projections. The flag is unique up to block rotations, so the factorization is a property of the hierarchy rather than of a particular basis.","pith_inferences":["The exactness condition suggests a diagnostic for downstream use: run a rank-increment check before applying Flag-BMGS, so that invalid hierarchies are rejected instead of silently producing approximations.","The decomposition points toward a hierarchy-aware analogue of PCA in which nested subspaces, rather than principal directions, are the preserved quantities; a statistical model for flag-type estimation under noise would be a natural next step.","The few-shot distance of Eq. (15) is differentiable, so fine-tuning the feature extractor with a flag-classifier loss is a direct extension the paper leaves open.","Because the flag is determined only up to block rotations, distances between flag representations are invariant to the particular Stiefel coordinates chosen, making the representation well suited to clustering and averaging on the flag manifold."],"forward_implications":["Any matrix whose nested column groups have strictly increasing ranks can be factored exactly as D=QRP^T with a hierarchy-preserving flag in Stiefel coordinates (Prop. 3).","Flag-BMGS computes this decomposition block by block, with cost equal to k SVDs on the hierarchy blocks; the IRLS-SVD variant (RFD) handles outlier columns by using an L1 objective.","Truncating the flag type gives a low-rank reconstruction that preserves the column hierarchy, which SVD- and QR-based reconstruction do not; this is what drives the reported gains in hyperspectral image denoising.","Flag prototypes for few-shot learning embed all shots of a class into a single flag and score queries by projection residuals; on AlexNet features the flag classifier matches or improves Euclidean and subspace prototypes in the tested 5-way tasks.","Chordal distances between flags, computed from the decomposition, give distance matrices and MDS embeddings that cluster noisy hierarchical datasets more cleanly than Euclidean or SVD-based distances."],"supporting_citations":[{"why":"Supplies the Stiefel-coordinate representation of flags and the quotient description of the flag manifold used in Definitions 3 and 4.","marker":"[60]"},{"why":"Provides the block modified Gram-Schmidt procedure that Flag-BMGS adapts for hierarchy-preserving factorization.","marker":"[3]"},{"why":"Contributes the block Gram-Schmidt algorithm and stability analysis that Flag-BMGS builds upon.","marker":"[19]"},{"why":"Justifies using SVD for reliable subspace recovery within each block of the algorithm.","marker":"[10]"},{"why":"Defines the Euclidean prototypical-network baseline that flag classifiers are compared against in few-shot learning.","marker":"[51]"},{"why":"Defines the subspace-classifier baseline for few-shot learning that flag classifiers are compared against.","marker":"[50]"},{"why":"Provides chordal averaging and geometry on flag manifolds used for distances and clustering of flag representations.","marker":"[33]"}],"fun_headline_variants":["Flag decomposition exactly captures hierarchical data","Exact flag factorization for nested subspace data","Hierarchical data admit precise flag factorization","New flag method preserves nested subspaces exactly"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every nested column group increases the column rank, so that the subspaces spanned by [D_{A_i}] are strictly nested; if a supplied hierarchy violates this (or, in the few-shot application, if early-layer features do not actually lie in the span of the full features), the exact decomposition does not exist.","fun_headline_variants_meta":{"raw":{"variants":["Flag decomposition exactly captures hierarchical data","Exact flag factorization for nested subspace data","Hierarchical data admit precise flag factorization","New flag method preserves nested subspaces exactly"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000194,"raw_usage":{"total_tokens":1312,"prompt_tokens":859,"completion_tokens":453,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":475,"completion_tokens_details":{"reasoning_tokens":401}},"tokens_in":475,"tokens_out":453,"duration_ms":4730,"temperature":1.0,"reasoning_tokens":401,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T11:35:49.496982+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the ranks of [D_{A_i}] for a concrete dataset with a proposed hierarchy; if any two consecutive groups have equal rank, the if-and-only-if theorem says no exact flag decomposition exists, so Flag-BMGS output cannot be hierarchy-preserving. Concretely, duplicating a column across two nested groups makes the rank increments vanish. For the few-shot claim, one can numerically check whether the span of early-layer AlexNet features is contained in the span of the full features on the actual support set; a counterexample would invalidate the flag-prototype distance.","supporting_citations":[{"cited_title":"Optimiza- tion on flag manifolds.Mathematical Programming, 194(1): 621–660, 2022","cited_arxiv_id":null,"evidence_quote":"Supplies the Stiefel-coordinate representation of flags and the quotient description of the flag manifold used in Definitions 3 and 4."},{"cited_title":"Block modified Gram–Schmidt algorithms and their analysis.SIAM Journal on Matrix Analysis and Applications, 40(4):1257–1290, 2019","cited_arxiv_id":null,"evidence_quote":"Provides the block modified Gram-Schmidt procedure that Flag-BMGS adapts for hierarchy-preserving factorization."},{"cited_title":"Stability analysis and improvement of the block Gram–Schmidt algorithm.SIAM journal on scientific and statistical computing, 12(5):1058– 1073, 1991","cited_arxiv_id":null,"evidence_quote":"Contributes the block Gram-Schmidt algorithm and stability analysis that Flag-BMGS builds upon."},{"cited_title":"SIAM, 1997","cited_arxiv_id":null,"evidence_quote":"Justifies using SVD for reliable subspace recovery within each block of the algorithm."},{"cited_title":"Prototypical networks for few-shot learning.Advances in neural informa- tion processing systems, 30, 2017","cited_arxiv_id":null,"evidence_quote":"Defines the Euclidean prototypical-network baseline that flag classifiers are compared against in few-shot learning."},{"cited_title":"Adaptive subspaces for few-shot learn- ing","cited_arxiv_id":null,"evidence_quote":"Defines the subspace-classifier baseline for few-shot learning that flag classifiers are compared against."},{"cited_title":"Chordal averaging on flag manifolds and its applications","cited_arxiv_id":null,"evidence_quote":"Provides chordal averaging and geometry on flag manifolds used for distances and clustering of flag representations."}],"review_version":1}