acceptodds
Under review as a conference paper at ICLR 2027

Underdetermined Polytopic Matrix Factorization: Identifiability via Determinant Maximization and Face-Span Geometry

Abstract

Structured matrix factorization supports analytical representation learning by recovering latent vectors from unknown linear mixtures through structural constraints. Nonnegativity, sparsity, and antisparsity motivate nonnegative matrix factorization, sparse component analysis, and bounded component analysis, respectively. Polytopic matrix factorization (PMF) unifies these approaches through a prescribed polytopic domain, allowing different combinations of structural properties, e.g., nonnegative sparse coefficients with signed, amplitude bounded coefficients in the same representation. Existing PMF identifiability, however, requires at least as many measurements as latent components. We extend PMF to the underdetermined regime, with fewer measurements than latent components, while retaining its source correlation determinant-maximization (Det-Max) criterion. Our approach combines PMF’s maximum-volume inscribed ellipsoid based sufficient scattering condition with a face-span skeleton formed by intersecting the polytope with linear spans of low-dimensional faces. Under explicit assumptions on cell population, relations among face spans, and local injectivity of the mixing matrix, we establish finite-sample exact recovery from noiseless observations: every global maximizer recovers the mixing matrix and all latent samples up to linear automorphism of the polytope. We derive sufficient measurement dimension conditions determined by the face-span geometry, demonstrate that Det-Max can exclude coordinate-mixing ambiguities, and establish a vanishing-regularization characterization of Det-Max through a source-entropy and reconstruction objective. These results provide a geometric foundation for underdetermined PMF, with implications for overcomplete dictionary learning with structural constraints tailored to different groups of latent coefficients.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Matrix Factorization, Underdetermined Matrix Factorization, Identifiability, Polytopic Matrix Factorization, Determinant Maximization, Correlative Information Maximization, Overcomplete Dictionary Learning, Structured Representation Learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_ondMOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies underdetermined polytopic matrix factorization, where both the mixing matrix and latent coefficients must be recovered with fewer measurements than latent dimensions. The method restricts latent variables to a union of low-dimensional face spans and uses determinant maximization to resolve the remaining ambiguity up to polytope symmetries. The main contribution is theoretical identifiability, with supporting synthetic experiments and image dictionary examples.

Critical strengths
  1. The main contribution is a meaningful extension of polytopic matrix factorization to the underdetermined setting where the number of measurements is smaller than the latent dimension. The face-span structure gives a way to recover a common linear transformation even when standard reconstruction alone is not enough.

  2. I also found the separation between the structural recovery step and the determinant maximization step useful. It makes clear which ambiguities can be removed from the data structure and which require the polytope geometry.

Critical weaknesses
  1. The theoretical assumptions are quite strong. In particular, the required number of samples can become extremely large compared with the sample sizes used in the experiments.

  2. There is still a clear gap between the theory and the practical solver. The main results assume noiseless observations and global optima, while practical recovery under realistic noise and finite optimization is not established. The image dictionary experiments are also mainly qualitative.

Questions for authors

How robust is the recovery when the observations are noisy or when samples only approximately satisfy the face-span assumptions?

Can the authors comment on whether the large sample requirement is mainly a proof artifact or is actually necessary in difficult cases?

For the image dictionary experiments, can the authors provide quantitative comparisons with standard dictionary learning methods?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Comments (Part 1)

We thank the reviewer for the positive and constructive comments. Below we describe how the revised article addresses the suggestions by the reviewer and we also provide our responses to the comments and questions.

Q.1, CW2: noise and finite optimization... robustness to noise and approximate face-span membership

We thank the reviewer for highlighting these important areas for improvement. The revised manuscript adds quantitative evaluations of the finite-iteration solver under observation noise and approximate skeleton membership. We also clarify the distinction between the theoretical identifiability guarantee and the empirical performance of the practical solver. Quantitative comparisons on natural-image data are provided in our response to Q3 below.

The theorem establishes conditions under which the objective identifies the generating factors; numerical convergence is evaluated separately.

For observation noise, we use Y=HgSg+W\mathbf Y=\mathbf H_g\mathbf S_g+\mathbf W, with Gaussian noise scaled so that 10log⁡10(∣HgSg∣F2/∣W∣F2)=3010\log_{10}(\\|\mathbf H_g\mathbf S_g\\|_F^2/\\|\mathbf W\\|_F^2)=30 dB. For approximate skeleton membership, we use Sδ=0.95Sg+0.05Z\mathbf S_\delta=0.95\mathbf S_g+0.05\mathbf Z, with the columns of Z\mathbf Z sampled uniformly inside the source polytope. Perturbed sources are not projected back onto the skeleton, while the solver retains its original constraint; this condition retains the essentially noiseless baseline observations.

Appendices K.2–K.4 now report sensitivity experiments across all four canonical polytopes and both face dimensions, retaining the baseline optimization settings: 3,000 updates per initialization, five initializations selected by objective value, and ten data repetitions. Evaluation includes jointly aligned source and mixing-matrix errors without gain fitting, alongside reconstruction error and SIR. At r=25r=25, M=20M=20, N=3200N=3200, and k0=3k_0=3, adding 30 dB Gaussian observation noise increases mean source errors from 1.27% to 2.96% for B1B_1 and from 2.57% to 3.34% for B1,+B_{1,+}. Under the separate approximate-membership experiment, the corresponding errors are 4.49% and 4.15%. The complete results show how sensitivity varies with source geometry and sample size (Figures 12–13 and Table 4).

Q2, CW1: sample complexity

The large sample requirement arises from a specific worst-case step: each incorrect candidate cell image can contain at most p−1p-1 designated general-position samples from a true cell, so J(p−1)+1J(p-1)+1 samples force a match against all JJ candidates, where p=k0+1p=k_0+1. Applying this argument separately to every cell yields the stated count. This counting step does not exploit the additional coupling between candidate cells imposed by their common mixing matrix, leaving scope for sharper analysis.

The experiments provide quantitative evidence that accurate joint recovery occurs far below this sufficient count. For example, at r=25,p=4r=25,\\ p=4, with M=20M=20 and only N=3200N=3200, both source and mixing-matrix mean relative errors are below 3% for the signed and nonnegative ℓ1\ell_1 models, without gain fitting (Appendix K.4). These results establish recovery accuracy in the tested settings; they do not certify the theorem’s hypotheses or prove a smaller identifiability bound.

Closing the gap requires more than improving the numerical constant: the experiments use fewer samples than the number of cells, so a sharper theory must also weaken exhaustive cell coverage and address the scattering requirement. Conditions based on informative subsets of cells, their shared geometric constraints, and quantitative scattering under specified sampling models are therefore valuable research directions. The present results motivate such a theory while keeping the distinction between proved identifiability conditions and observed finite-sample recovery explicit.

AuthorsOpenReview ↗

Response to Reviewer Comments (Part 2)

Q.3, CW2: Quantitative dictionary-learning comparisons

We added quantitative comparisons of UPMF (B1,+B_{1,+}), K-SVD, and Online ℓ1\ell_1 DL, including nonnegative-coefficient variants (NN). Here B1,+B_{1,+} is one instance of the source priors supported by UPMF. The comparisons report reconstruction SNR and Gabor-fit quality, measuring reconstruction accuracy and spatial filter structure, respectively.

The table evaluates every learned dictionary on the same validation patches using nonnegative orthogonal matching pursuit (NN-OMP), with at most ten active atoms per patch. This shared encoder compares dictionary quality; UPMF retains its own KϵK_\epsilon training procedure. Higher SNR means lower reconstruction error. “Whitened” refers to preprocessed patches and “pixel-subspace” to reconstruction mapped back to the retained PCA components; these values are distinct from denoising PSNR.

MethodWhitened SNR (dB)Pixel-subspace SNR (dB)Gabor fits with R2≥0.9R^2\ge0.9 (%)
UPMF (B1,+B_{1,+})5.726.1874.3
K-SVD5.525.6350.8
K-SVD-NN5.765.8457.2
Online ℓ1\ell_1 DL5.404.5868.7
Online ℓ1\ell_1 DL-NN5.785.0072.6

SNR values are means over three training runs. Gabor-fit percentages cover all 10001000 atoms of each reference-run dictionary.

UPMF combines comparable whitened reconstruction with the highest pixel-subspace SNR and fraction of atoms above the stated Gabor-fit threshold. Section K.8.2 (“Image-patch dictionary comparison”), Table 7 and Figure 19, provides the full reconstruction results, curves across atom budgets, and method details. Section K.5, Figure 15, shows the Gabor-fit distribution and atom/fit/residual examples.

Thank you for adding the experiments on noise robustness, approximate membership, and dictionary learning. They substantially strengthen the empirical evaluation, though the high theoretical sample complexity remains a notable limitation.

We appreciate your constructive feedback, which helped us strengthen the empirical evaluation and improve the manuscript.

Reviewer_iBCSOpenReview ↗
Rating
3
Confidence
3(+1)
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the identifiability of underdetermined polytopic matrix factorization (PMF), where the latent dimension exceeds the observation dimension. To address the additional ambiguities introduced by the nontrivial nullspace of the mixing matrix, the authors introduce a face-span skeleton that constrains latent samples to a union of low-dimensional linear slices of a prescribed polytope.

The theoretical analysis proceeds in two stages. First, under assumptions involving relation completeness, local injectivity, and sufficient cell population, the authors show that every exact feasible factorization is related to the ground-truth factors through a single invertible linear transformation. Second, under a sufficient scattering condition, determinant maximization restricts the remaining transformations to the linear automorphism group of the source polytope.

The paper also derives explicit conditions for four canonical polytopes, constructs an octagon example exhibiting nontrivial coordinate-mixing ambiguities, and proposes batch and online algorithms with synthetic and image-patch dictionary-learning experiments.

Critical strengths
  1. Meaningful theoretical extension. Extending PMF identifiability to the underdetermined regime is an interesting and challenging problem. The proposed framework addresses an important limitation of earlier full-column-rank PMF analyses.

  2. General geometric modeling framework. The face-span skeleton provides a unified representation of several structured latent models, including coordinate-sparse, nonnegative, and certain non-coordinate low-dimensional models.

  3. Detailed supplementary material. The appendices provide extensive proofs, geometric explanations, algorithmic derivations, and experimental settings.

Critical weaknesses
  1. Insufficient comparisons with existing methods. The experiments mainly report synthetic recovery results and qualitative visualizations of learned dictionaries, without direct comparisons with established methods. Consequently, the practical advantages of the proposed approach remain unclear. Quantitative comparisons are needed to demonstrate the effectiveness of the face-span skeleton and Det-Max objective.

  2. Robustness. The theoretical analysis assumes exact face-span skeleton membership and known source geometry. How robust is the proposed method when source samples only approximately satisfy the skeleton constraint, or when the assumed polytope and face dimension are misspecified? Could the authors provide a stability analysis or sensitivity evaluation under such conditions?

Questions for authors
  1. Theory: The identifiability theory relies on the (q)-relation completeness condition. Beyond the studied polytopes, how can this property be verified for general non-coordinate polytopes? Could the authors further clarify how restrictive this assumption is?

Assumption 3.3 requires sufficient samples in every cell. Could identifiability still be established when only a subset of cells is populated?

The framework assumes that the source polytope and face dimension are known. How sensitive are the identifiability results to misspecified priors or source samples that only approximately satisfy the skeleton constraint?

  1. Experiments: Could the authors provide quantitative comparisons with established overcomplete dictionary-learning methods, such as K-SVD and classical online dictionary learning, under comparable experimental settings?

In particular, it would be valuable to evaluate reconstruction accuracy, representation sparsity, and computational efficiency on the natural-image datasets. For synthetic experiments, comparisons using source and mixing-matrix recovery errors would also help assess the benefits of the proposed framework.

In the Octagon experiment, gain calibration and local optimization recover only 18/76 near-exact fits, while 76/76 recovery requires additional geometry-specific 45° reorientation proposals. Can the proposed Det-Max optimization resolve coordinate-mixing ambiguities without such tailored candidate searches? Experiments on other non-coordinate polytopes would help demonstrate the generality of the proposed algorithm.

Appendix K.6 indicates that a trace-based criterion ranks the fixed Octagon candidates identically to Det-Max. Could the authors clarify the advantages of Det-Max over alternative spread-promoting objectives, possibly by providing an example where a simpler criterion fails?

4 comments
AuthorsOpenReview ↗

Response to Reviewer Comments (Part 1)

We appreciate the reviewer's positive comments and constructive suggestions. Below, we describe how the revised article addresses them and provide our response to the comments and questions.

CW1, Experiments Q1: Comparisons with existing methods.

We thank the reviewer for this constructive suggestion. We have added direct comparisons with K-SVD/OMP, K-SVD with exact support enumeration for the sparse models, and Online ℓ1\ell_1 dictionary learning, including nonnegative coefficient adaptations where appropriate. All methods receive identical observations with r=25r=25, N=6000N=6000, k0=1k_0=1, and M∈{10,15,20}M\in\{10,15,20\}, using ten data repetitions. Appendix K.8.1, Figure 18, and Table 6 provide implementation details and comparisons of dictionary atom recovery, SIR, gain calibrated source error, and reconstruction error.

These evaluations address UPMF’s central contribution: joint dictionary–source recovery under prescribed polytopic priors, for both coordinate-sparse and dense, structured sources.

For sparse B1B_1 sources at M=20M=20, UPMF recovers 97.6% of dictionary directions with 7.85% source error, compared with 97.6%/14.96% for K-SVD/OMP and 99.2%/21.38% for Online ℓ1\ell_1 DL. The results also identify settings favoring other methods: for nonnegative sparse sources, exact coding K-SVD achieves the lowest source error, 6.44%, versus 13.51% for UPMF.

The cube-based experiments demonstrate the value of incorporating structure beyond coordinate sparsity. At M=20M=20, UPMF recovers 100% and 92.4% of dictionary directions, with source errors of 4.80% and 23.71%, for the signed and nonnegative cubes, respectively; the tested sparsity-based baselines recover no dictionary directions. These comparisons contrast structural priors: UPMF exploits the dense face-span structure of these sources.

We have also added quantitative natural-image comparisons on 40,000 held-out patches, evaluating all learned dictionaries with common Orthogonal Matching Pursuit (OMP) and nonnegative OMP encoders at matched atom budgets (Appendix K.8.2). UPMF achieves comparable whitened reconstruction accuracy and the highest mean pixel-subspace SNR at the ten-atom budget under both encoders. Details are in our response to Experiments Q2 below.

Together, these comparisons demonstrate the effectiveness of the face-span-constrained Det-Max formulation for joint recovery under different source priors.

CW2: Robustness to approximate skeleton membership and misspecified geometry.

We thank the reviewer for raising this question. We have added controlled sensitivity experiments that separately test observation noise and departures from exact face-span skeleton membership, retaining the baseline optimization settings and the solver’s skeleton constraint.

For observation noise, we use Y=HgSg+W\mathbf Y=\mathbf H_g\mathbf S_g+\mathbf W, with Gaussian noise scaled to an observation SNR of 3030 dB. For approximate skeleton membership, we generate Sδ=(1−δ)Sg+δZ\mathbf S_\delta=(1-\delta)\mathbf S_g+\delta\mathbf Z with δ=0.05\delta=0.05, where the columns of Z\mathbf Z are sampled uniformly inside the source polytope. This construction preserves polytope membership but generally violates skeleton membership, while retaining the essentially noiseless baseline. It thus tests an exact skeleton constraint on approximately conforming data.

Both experiments cover all four canonical polytopes and k0∈{1,3}k_0\in\{1,3\}, with sample-size sweeps, ten data repetitions, and objective-based selection among five initializations per repetition. Recovery is evaluated against the actual generating sources, Sg\mathbf S_g for the noise experiment and Sδ\mathbf S_\delta for the membership experiment, using eS=∥S^−QS⋆∥F/∥S⋆∥Fe_{S}=\lVert\widehat{\mathbf{S}}-\mathbf{Q}\mathbf{S}_{\star}\rVert_{F}/\lVert\mathbf{S}_{\star}\rVert_{F}. The same admissible permutation or signed permutation Q\mathbf Q aligns both estimated factors, without gain fitting.

At r=25r=25, M=20M=20, N=3200N=3200, and k0=3k_0=3, the mean relative source errors are:

Source polytopeBaseline30 dB noiseδ=0.05\delta=0.05
B1B_11.27%2.96%4.49%
B1,+B_{1,+}2.57%3.34%4.15%
B∞B_\infty9.75%12.55%12.24%
B∞,+B_{\infty,+}10.86%16.89%17.80%

Accurate source recovery persists for the two ℓ1\ell_1 models under both deviations, with errors below 5%, while the cube-based models are more sensitive.

The protocol, alignment metrics, and results are in Appendices K.2, K.3, and K.4 (“Robustness to observation noise” and “Robustness to approximate face-span membership”; Figures 12–13, Table 4). These experiments provide empirical robustness evidence at the tested noise and perturbation levels. They retain the prescribed polytope and face dimension; we test face-dimension misspecification separately in our response to Theory Q3 below, while general stability guarantees remain a separate question.

AuthorsOpenReview ↗

Response to Reviewer Comments (Part 2)

Questions For Authors

Theory Q1: Verifiability and restrictiveness of relation completeness.

We thank the reviewer for this question. Relation completeness is a checkable geometric condition, including for non-coordinate polytopes. It ensures that consistency among small groups of face spans forces consistency with one global linear map, as formalized in Appendix F.1.

Appendix G.1 provides a general verification procedure. Choose a basis matrix Ua\mathbf U_a for each distinct face span and concatenate them into U\mathbf U. Compute the nullspaces of all submatrices UI\mathbf U_I involving at most qq spans, and embed their basis vectors into the full coefficient space by zero-padding. If Rq\mathbf R_q collects these vectors, relation completeness holds exactly when

=\dim\ker\mathbf U.$$ The same matrices give $d_q=\max_{|I|\le q}\operatorname{rank}(\mathbf U_I)$. This provides a finite certificate using exact arithmetic, although enumeration can be costly for large arrangements. The substantive restriction is that this test must succeed for a $q$ satisfying **$d_q\le M<r$**. Taking $q$ large enough makes relation completeness automatic, but may increase $d_q$ to $r$, eliminating the underdetermined guarantee. Thus, the assumption requires global dependencies to be generated by relations among groups of sufficiently small combined dimension. It is not tied to coordinate alignment: both relation completeness and $d_q$ are preserved under invertible linear transformations. These are explicit sufficient conditions; failure of the test excludes the arrangement from our guarantee, rather than establishing impossibility of recovery. As a concrete non-coordinate example, we applied this certificate to the heterogeneous product polytope $\mathcal P_\times$ of Appendix K.9. Its $108$ distinct edge spans are $2$-relation-complete with $d_2=4$, so the experiment's $M=4<r=6$ satisfies Assumption 3.1. > Theory Q2: Identifiability when only a subset of cells is populated. The all-cell requirement is a sufficient condition, not a claim of necessity. Partial coverage may still support identifiability, provided the populated cells determine the full latent space and their correspondences and relations force a single ambient transformation. The samples must also satisfy the sufficient-scattering condition used by Det-Max to resolve the remaining ambiguity. However, an arbitrary subset is insufficient. If the occupied spans lie in a proper subspace, the mixing matrix’s action outside that subspace is unobservable; even spanning the full space does not by itself resolve competing cell assignments. Assumption 3.3 supplies an explicit coverage condition that guarantees the cell-matching step in our proof. A partial-coverage theorem would require a weaker, geometry-dependent condition ensuring this same consistency; it does not follow simply by reducing the number of cells in the present theorem.
AuthorsOpenReview ↗

Response to Reviewer Comments (Part 3)

Theory Q3: Known polytope and face dimension; sensitivity to misspecification.

UPMF constrains latent vectors to a prescribed source polytope, which expresses structural assumptions such as nonnegativity, sparsity, and boundedness. This knowledge of the source domain is also assumed in existing PMF theory for the (over)determined setting. In UPMF, the face dimension k0k_0 additionally specifies the face-span skeleton. For the ℓ1\ell_1 domains, this gives bounded pp-sparsity with p=k0+1p=k_0+1; for other polytopes, it specifies low-dimensional, potentially non-coordinate face spans.

The polytope and face dimension are prescribed, rather than inferred.

To address the reviewer's question on face-dimension misspecification, we performed the following test for the B1B_1 and B∞B_\infty source polytopes. Data are generated with k0=3k_0=3 under the baseline robustness protocol (r=25r=25, M=20M=20, N=3200N=3200, ten data repetitions, five initializations per repetition). The unchanged solver is run with a fitted face dimension k^0∈2,3,4,5\hat k_0\in\\{2,3,4,5\\}. Mean errors (%), jointly aligned without gain fitting:

B1B_1B∞B_\infty
k^0\hat k_0eSe_SeHe_HeYe_YeSe_SeHe_HeYe_Y
2 (under)48.7422.0443.5722.935.7016.69
3 (true)1.301.17<0.0019.540.493.86
4 (over)2.302.22<0.00110.020.793.56
5 (over)2.722.65<0.00110.640.893.15
  • Underestimating k0k_0 excludes the generating sources from the fitted skeleton, and recovery fails for both polytopes, detectably: the observation error rises to 43.57% for B1B_1 and 16.69% for B∞B_\infty.
  • Overestimating k0k_0 degrades recovery gracefully: the source error increases from 1.30% to at most 2.72% for B1B_1, and from 9.54% to at most 10.64% for B∞B_\infty.

Thus, choosing k0k_0 plays a role analogous to choosing a sparsity budget: a modest overestimate is tolerated in these experiments, while an underestimate is flagged by the reconstruction residual. We anticipated this tolerance because higher-dimensional face-span skeletons contain the lower-dimensional ones, preserving feasibility of the generating sources. These findings are empirical: with an overestimated k^0\hat k_0, the data do not populate all cells of the fitted skeleton, so they lie outside our theorem's cell-population assumption.

Experiments Q2: Evaluation metrics for the natural-image and synthetic experiments.

We have expanded the evaluation to quantify factor recovery and reconstruction accuracy.

For synthetic data, we report

e_H=\frac{\\|\widehat H-H_gQ^{-1}\\|_F}{\\|H_g\\|_F},\qquad e_Y=\frac{\\|Y-\widehat H\widehat S\\|_F}{\\|Y\\|_F}.$$ Here, $S_\star$ contains the actual generating sources, including perturbations where applicable. A single admissible permutation or signed permutation $Q$ minimizes $e_S^2+e_H^2$, with no gain or offset fitting. Percentages are relative norm errors multiplied by $100$. At $r=25$, $M=20$, $N=6000$, and $k_0=3$, UPMF achieves mean (source,mixing)-matrix errors of **(0.95%, 0.84%)** for $B_1$ and **(2.73%, 2.56%)** for $B_{1,+}$, with observation errors below $0.002$% in both cases. Appendices K.3–K.4, Table 3, and Figures 10–11 provide definitions and results across all four polytopes and both face dimensions. Cross-method comparisons additionally use a common dictionary-scale calibration (K.8.1). For natural images, all dictionaries are evaluated on 40,000 patches with common encoders and matched atom budgets. With nonnegative OMP and a ten atom budget, UPMF achieves 6.18 dB pixel-subspace SNR, versus 5.84 dB for K-SVD-NN and 5.00 dB for Online $\ell_1$ DL-NN. This measures reconstruction within the retained PCA subspace. Gabor fitting provides a descriptive measure of filter shape: $74.3$% of its reference dictionary’s atoms attain $R^2\ge0.9$, moreover, $83.2$% of the atoms obtain $R^2\ge0.8$. K.8.2, Table 7, and Figure 19 report reconstruction comparisons at matched atom budgets; K.5 and Figure 15 detail the Gabor analysis. Table 7 also reports representation sparsity under each method’s own encoder; UPMF uses an average of 8.40 active coefficients per validation patch under its ten-atom constraint. For computational efficiency, we report implementation details and training budgets. We have not conducted runtime comparisons as the focus of this work is theoretical identifiability rather than speed improvement of algorithms.
AuthorsOpenReview ↗

Response to Reviewer Comments (Part 4)

Experiments Q3: Octagon experiment and other non-coordinate polytopes.

The octagon experiment separates the objective’s ability to distinguish factorizations from the solver’s ability to find them. In the reported experiment, local polishing did not correct the mixed orientations; the 45∘45^\circ proposals were needed. However, the fixed-candidate comparison isolates the objective’s contribution: reconstruction tied in all 456 block comparisons, whereas the Det-Max consistent objective favored correcting all 9191 mixed blocks and retaining the remaining 365. The proposals use the known polytope geometry, and acceptance depends solely on objective improvement (Appendix K.6). They are not tuned to the ground truth: they are the arrangement symmetries that are not polytope symmetries (for the octagon, one 45∘45^\circ reorientation per coordinate block), which can be enumerated from the face-span arrangement itself.

Following the reviewer’s suggestion, we added recovery experiments on a different non-coordinate, heterogeneous product polytope, P×\mathcal{P}_\times, combining overlapping ℓ1\ell_1 constraints and partial nonnegativity, with r=6r=6, M=4M=4, and k0=1k_0=1. The solver uses projected updates of Kϵ,λK_{\epsilon,\lambda}, followed by cellwise least-squares source refinement and dictionary refitting, accepting only improvements in the same objective. It enumerates the polytope’s 108108 face span cells for projection and refinement, without polytope-specific proposals.

Across ten data repetitions with ten initializations each, mean (source, mixing)-matrix error is (1.02%, 1.05%) at N=750N=750; mean observation error is below 0.002%. Both factors are aligned using a common polytope automorphism, without gain fitting. Appendix K.9, Figure 20, and Table 8 provide the complete results and implementation details.

This additional experiment demonstrates accurate joint recovery beyond the octagon geometry. The evidence supports the objective’s ambiguity selection role and its use with other source geometries; it does not establish that unaugmented local updates can resolve every coordinate mixing ambiguity.

Experiments Q4: Det-Max versus trace and other spread criteria.

We thank the reviewer for this insightful observation, which motivates an important clarification of the advantages of Det-Max. The statement in K.6 concerns fixed-candidate rankings, not a separate trace-based optimization experiment. Both criteria favor the correct octagon candidate because the competing rotation–contraction reduces both volume and total source energy. The advantage of Det-Max is its identification guarantee under the stated assumptions; trace, tr⁡(RS)=∣S∣F2/N\operatorname{tr}(R_S)=\\|S\\|_F^2/N, does not generally provide that guarantee.

A concrete counterexample follows from rescaling the same octagon domain by T=diag⁡(2,1,…,1)T=\operatorname{diag}(2,1,\ldots,1). Let u=e1+e2u=e_1+e_2, and choose the feasible rotation–contraction BB so that Bu=(6/5)e1Bu=(6/5)e_1. Then

=5 <\\|TBu\\|_2^2=\frac{144}{25}.$$ Thus, this incorrect transformation produces more energy than every correct representative for this sample. Starting with the finite source construction satisfying cell population and scattering in Appendix I.3, append sufficiently many copies of $u$, retaining all original witness samples, and apply $T$. These operations preserve the required conditions. The strict energy inequality then makes trace prefer the incorrect feasible sources $TBS$ over every correct representative $TQS$, although both factorizations reconstruct the observations exactly. In contrast, $$\frac12\log\det R_{TBS} -\frac12\log\det R_{TS} =\log|\det B| =\log(18/25)<0.$$ Det-Max therefore rejects this incorrect candidate. This analytical counterexample concerns the unregularized source objectives and demonstrates why agreement on the original octagon candidates does not make trace a general substitute for Det-Max.

Comments on the paper

4 comments
AuthorsOpenReview ↗

General response to reviewer comments and revisions to manuscript

We sincerely thank the reviewers for their careful reading and for the time and effort they devoted to our submission. We are grateful for their positive assessments and for their constructive comments, which helped us strengthen the paper.

We revised the article to address the suggestions provided by the reviewers, which improved the article. Below is the list of changes to the article in the revision, followed by the list of main points from our responses.

Changes in the revision

  1. Comparisons with established methods (Appendix K.8; iBCS, ondM).
    • Synthetic recovery. We compare UPMF with K-SVD/OMP, K-SVD with exact support enumeration, and Online ℓ1\ell_1 dictionary learning, including nonnegative-coefficient variants. All methods receive identical data (r=25r=25, k0=1k_0=1, M∈{10,15,20}M\in\{10,15,20\}). We report atom recovery, SIR, source error and reconstruction error (Fig. 18, Table 6).
    • Natural images. All dictionaries are evaluated on 40,000 held-out patches with common Orthogonal Matching Pursuit (OMP) and Non-Negative Orthogonal Matching Pursuit (NN-OMP) encoders at matched atom budgets, over three training seeds (Fig. 19, Table 7).
  2. Joint factor-recovery metrics (Appendices K.3–K.4; hHjx, iBCS). We report source, mixing-matrix and observation errors eSe_S, eHe_H, eYe_Y. Both factors are aligned by a single admissible polytope automorphism. Results cover all four canonical polytopes and both face dimensions (Table 3, Figs. 10–11).
  3. Robustness experiments (Appendices K.2, K.4; iBCS, ondM). We add sample-size sweeps under 30 dB observation noise and under approximate face-span membership (δ=0.05\delta=0.05), for all four polytopes and k0∈{1,3}k_0\in\{1,3\} (Figs. 12–13, Table 4).
  4. A heterogeneous, non-coordinate source polytope (Appendix K.9; iBCS). We show joint recovery on a polytope corresponding to heterogeneous features, which combines overlapping ℓ1\ell_1 constraints with partial nonnegativity (Fig. 20, Table 8).
  5. Quantitative characterization of learned image atoms (Appendix K.5; ondM). We fit Gabor functions to all 1000 UPMF atoms and report the statistics (Fig. 15).

Main points from our responses

  • UPMF is competitive on sparse models and effective beyond sparsity. With M≥15M\ge15 measurements, UPMF matches or exceeds the baselines on sparse models; for B1B_1 at M=20M=20, it recovers 97.6% of atoms with 7.85% source error, versus 14.96% for K-SVD/OMP and 21.38% for Online ℓ1\ell_1 DL. For dense cube sources (B∞B_\infty, B∞,+B_{\infty,+}), UPMF recovers 100% and 92.4% of atoms, whereas the tested sparsity-based baselines recover none. With M≥15M \geq 15, UPMF attains the highest SIR in every sparse setting.
  • Natural images. At a ten-atom budget, UPMF achieves the highest pixel-subspace SNR under both common encoders (6.66 dB with OMP, 6.18 dB with NN-OMP), with comparable whitened SNR. Moreover, 74.3% of its atoms are fit by Gabor functions with R2≥0.9R^2\ge0.9.
  • Accurate joint recovery, including amplitudes. At r=25r=25, M=20M=20, N=6000N=6000, k0=3k_0=3, the (source, mixing)-matrix errors are (0.95%, 0.84%) for B1B_1 and (2.73%, 2.56%) for B1,+B_{1,+}. eSe_S includes the component that SIR cannot see. These errors therefore directly address the limitations of SIR raised by Reviewer hHjx.
  • Robustness. At N=3200N=3200 and k0=3k_0=3, source errors for both ℓ1\ell_1 models remain below 5% under 30 dB noise and under the δ=0.05\delta=0.05 membership perturbation, staying close to the baseline. The higher sensitivity of the cube models is quantified.
  • Sample complexity. J[J(p−1)+1]J[J(p-1)+1] is a worst-case sufficient count arising from the cell-matching step, not a necessary bound. Accurate recovery occurs far below it: errors are below 3% at N=3200N=3200 for r=25r=25, p=4p=4. We outline the directions required for a sharper theory.
  • Relation completeness is checkable. Appendix G.1 gives a finite rank certificate that applies to non-coordinate polytopes. The condition is invariant under invertible linear maps, and its substantive requirement is dq≤M<rd_q\le M<r. The all-cell assumption is sufficient, not necessary; we explain what a partial-coverage condition would require.
  • Det-Max versus trace. We give an analytical counterexample on a rescaled octagon. There, trace prefers an incorrect factorization that reconstructs the data exactly, while Det-Max rejects it. Det-Max's advantage is its theoretical identification guarantee.
  • Octagon and generality. Fixed-candidate comparisons isolate the objective's role: reconstruction ties in all block comparisons, whereas the Det-Max-consistent objective selects the correct orientation in every case. On the new heterogeneous polytope, source/mixing errors reach (1.02%, 1.05%) at N=750N=750.

We believe these additions strengthen both the empirical support and the clarity of our contributions.

AuthorsOpenReview ↗

Response to Reviewer Comments

We thank the reviewer for the positive comments and for raising improvement points. Below we describe how the revised article addresses the suggestions by the reviewer and we also provide clarification for the comments and questions.

CW1: Sufficient sample conditions.

The large sample requirement arises from a specific worst-case step: each incorrect candidate cell image can contain at most p−1p-1 designated general-position samples from a true cell, so J(p−1)+1J(p-1)+1 samples force a match against all JJ candidates. Applying this argument separately to every cell yields the stated count. This counting step does not exploit the additional coupling between candidate cells imposed by their common mixing matrix, leaving scope for sharper analysis.

The experiments provide quantitative evidence that accurate joint recovery occurs far below this sufficient count. For the reviewer’s r=25,p=4r=25,\\ p=4 setting, with M=20M=20 and only N=3200N=3200, both source and mixing-matrix mean relative errors are below 3% for the signed and nonnegative ℓ1\ell_1 models, without gain fitting (Appendix K.4). These results establish recovery accuracy in the tested settings; they do not certify the theorem’s hypotheses or prove a smaller identifiability bound.

Closing the gap requires more than improving the numerical constant: the experiments use fewer samples than the number of cells, so a sharper theory must also weaken exhaustive cell coverage and address the scattering requirement. Conditions based on informative subsets of cells, their shared geometric constraints, and quantitative scattering under specified sampling models are therefore valuable research directions. The present results motivate such a theory while keeping the distinction between proved identifiability conditions and observed finite-sample recovery explicit.

CW2: SIR and ambiguity reduction... joint recovery of HH and SS

We agree that SIR alone does not establish gain calibration or joint factor recovery. We, therefore, supplement it with direct errors in both factors, aligned using the same admissible polytope automorphism:

e_H=\frac{\\|\widehat H-H_gQ^{-1}\\|_F}{\\|H_g\\|_F},\qquad e_Y=\frac{\\|Y-\widehat H\widehat S\\|_F}{\\|Y\\|_F}.$$ For the canonical domains, $Q$ is a permutation or signed permutation, chosen jointly to minimize $e_S^2+e_H^2$. No gains or offsets are fitted. These metrics directly address both concerns. Nonunit gains cannot be absorbed into the allowed alignment. Moreover, writing $\widehat S=GS_g+\Delta$, with $\Delta S_g^\top=0$, gives $$\\|\widehat S-QS_g\\|_F^2 =\\|(G-Q)S_g\\|_F^2+\\|\Delta\\|_F^2.$$ Thus, the source error explicitly includes the discrepancy invisible to SIR, while the jointly aligned mixing-matrix error tests recovery of the corresponding dictionary. At $r=25$, $M=20$, $N=6000$, and $k_0=3$, the mean errors over ten repetitions are: | Polytope | $e_S$ (%) | $e_H$ (%) | $e_Y$ (%) | |---|---:|---:|---:| | $\mathcal{B}_1$ | 0.95 | 0.84 | 0.00104 | | $\mathcal{B}_{1,+}$ | 2.73 | 2.56 | 0.00186 | These values provide evidence of accurate joint recovery, including amplitudes, rather than component separation alone. Appendix K.3 defines the metrics; K.4, Table 3 and Figures 10–11 report all four polytopes and both face dimensions. Percentages are relative norm errors multiplied by 100. The revised sampling settings, are specified in K.2. The new metrics and evidence provided supports successful joint recovery of factors trough Det-Max optimization.

The reviewer thanks for the rebuttal and decide to keep the score.

We would like to thank the reviewer again for the feedback and the positive assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.