{"id":"e90fcadc-ad2c-452c-96ac-4a4eb6f18a0c","arxiv_id":"2411.10555","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"FRLC solves low-rank optimal transport by alternating semi-relaxed projections on two factors with a balanced Sinkhorn step on a latent coupling, yielding feasible iterates without Dykstra projections.","lead":"A new algorithm, FRLC, computes low-rank optimal transport plans using a latent coupling factorization that splits the optimization into three separate transport problems. The paper claims lower transport costs than prior low-rank solvers on synthetic data, spatial transcriptomics, and graph clustering applications.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The O(1/N) convergence guarantee rests on a uniform lower bound δ on inner marginals that Proposition E.5 asserts but does not prove; the cited Sinkhorn convergence bounds solver error, not the marginal gap induced by finite τ.","rationale":"The paper has two separable claims: (i) LC factorizations parameterize rank-r couplings and FRLC maintains feasibility without Dykstra projections; and (ii) FRLC converges at rate O(1/N). Claim (i) is well supported by the construction in Section 3.2 and the Cohen–Rothblum surjectivity argument, and the empirical sections give reproducible evidence that the method solves the low-rank OT objective well. The weak point is claim (ii). Proposition 3.4 inherits the block-descent convergence criterion only if the objective is block-smooth, and Proposition E.5 establishes smoothness only under a uniform lower bound δ on the entries of the inner marginals. The proof of that lower bound telescopes Sinkhorn sub-problem errors, but the relevant quantity is not a solver error: it is the gap between two different semi-relaxed solutions with different targets, and for finite τ this gap is controlled by the transport cost rather than by the number of Sinkhorn iterations. A small analytic example with an extreme cost shows that entries can be driven below any δ. This does not overturn the empirical contributions, and the gap may be repairable by adding a hard δ-constraint to the projection or by a different regularization argument, so a conditional verdict rather than rejection is appropriate.","tokens_in":49072,"tokens_out":11132,"duration_ms":109391,"concrete_test":"Compute the exact fixed point of the semi-relaxed projection (Algorithm 2) on a 2×2 instance with a = b = (1/2, 1/2), τ = 10, γ = 1, and first-iteration kernel K_Q derived from cost C = [[0, M], [M, 0]] with uniform initialization. Using the fixed-point formula q_i = b_i^s (K^T u)_i^{1−s}, where s = τ/(τ + γ^{−1}), check whether min_i q_i < δ = 1/4 for M = 10, 100, 10^4. If it is, the premise (38) in Proposition E.5 is violated at the first outer iteration, so the claimed smoothness constants and the O(1/N) rate do not follow from the stated argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central convergence claim (Proposition 3.4) depends on Proposition E.5, which needs every entry of g_Q and g_R to stay above δ so that the LLC objective is block-smooth with constants L = poly(‖C‖_F, n, m, r, δ). The proof of Proposition E.5 asserts that, for sufficiently large τ and N = O~(m²/ε) inner Sinkhorn iterations, one has ‖g_R^(k) − g_R^(k−1)‖ < ε = (1/r − δ)/N, and that telescoping these bounds yields a uniform lower bound δ. This does not follow. The τ regularizer in the semi-relaxed projection (Algorithm 2) penalizes the inner marginal toward the previous target g^(k−1), but the projection is still a semi-relaxed OT solve whose output marginal q satisfies q_i = b_i^s (K^T u)_i^{1−s}, where s = τ/(τ + γ^{−1}) < 1. For any finite τ, the linear transport cost can make some (K^T u)_i arbitrarily large, driving q_i toward zero. Pham et al. (2020) bounds the Sinkhorn solver's distance to the fixed point of that projection, not the distance between the fixed point and the target b. Thus the required δ-bound, and therefore the smoothness constants in Proposition E.5, are not established, and the non-asymptotic rate O(1/N) in Proposition 3.4 is unsupported. The feasibility/no-Dykstra claim and the empirical comparisons are not affected by this gap, but the stated convergence guarantee is.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces FRLC, a coordinate mirror-descent algorithm for low-rank optimal transport based on the latent-coupling (LC) factorization P = Q diag(1/g_Q) T diag(1/g_R) R^T, where T is a coupling between two distinct inner marginals g_Q and g_R. The main claims are that (i) the LC factorization parameterizes the rank-constrained coupling set Π_{a,b}(r) surjectively, so minimizing the LC objective is equivalent to the low-rank OT problem; (ii) FRLC decouples the optimization into three OT subproblems and remains feasible without Dykstra projections; (iii) FRLC converges with a non-asymptotic O(1/N) rate under a convergence criterion based on Ghadimi et al.; and (iv) FRLC extends to Wasserstein, Gromov-Wasserstein, and Fused Gromov-Wasserstein objectives with balanced, unbalanced, and semi-relaxed marginals. The paper supports these claims with a convergence analysis in Appendix E, an initialization analysis in Appendix F, and experiments on synthetic data, spatial transcriptomics, and graph partitioning.","tokens_in":49474,"tokens_out":16990,"duration_ms":159662,"significance":"If the claims are correct, the LC parameterization is a useful alternative to the factored couplings of Scetbon et al.: it decouples the low-rank OT problem into three OT subproblems, gives an interpretable latent coupling between two sets of barycenters, and naturally extends to unbalanced and semi-relaxed settings. The surjectivity argument for LCa,b(r) is sound and self-contained, the no-Dykstra feasibility structure is a genuine algorithmic advantage when implemented correctly, and the paper ships code and a broad experimental comparison. The improved low-rank approximation bound in Proposition E.7 is also a concrete contribution. However, two load-bearing points need work: the proof of the uniform lower-bound δ in Proposition E.5 does not establish the claimed marginal stabilization, and the pseudocode as printed contains swapped marginal conventions in the semi-relaxed projection and the Sinkhorn call, so the stated feasibility and convergence guarantees are not currently established for the algorithm as written.","major_comments":[{"comment":"The proof of Proposition E.5 does not establish the uniform lower bound δ on the inner marginals. The key assertion is that for sufficiently large τ and N = O~(m^2/ε) inner iterations one can guarantee ||g_R^(k) − g_R^(k−1)||_2 < ε = (1/N)(1/r − δ), and that telescoping these bounds yields g_{R,k,i} > δ for all i. However, the cited result of Pham et al. (2020) controls the distance between Sinkhorn iterates and the fixed point of the semi-relaxed projection for a fixed kernel; it does not control the gap between that fixed point and the previous target g_R^(k−1). In the semi-relaxed projection of Algorithm 2, the output marginal satisfies q_i = b_i^s (K^T u)_i^{1−s} with s = τ/(τ + γ^{−1}) < 1, so for any finite τ the transport cost can make (K^T u)_i arbitrarily large and drive q_i arbitrarily close to zero. The τ-regularization biases the marginal toward the previous iterate but does not, as proved here, enforce a uniform δ independent of C. Since the block-smoothness constants in Proposition E.5 are L_i = poly(||C||_F, n, m, r, δ), the non-asymptotic rate O(1/N) in Proposition 3.4 is unsupported. The authors should either prove the lower bound under explicit conditions on τ, γ, and C, or revise the convergence guarantee.","section":"Appendix E, Proposition E.5 and Proposition 3.4"},{"comment":"The pseudocode as printed does not implement the stated constrained updates, so the feasibility/no-Dykstra claim in Section 3.2 does not follow for the algorithm as written. In Algorithm 2, the update v ← b/K^T u makes the column sums of the returned diag(u)K diag(v) equal to b, i.e., the second marginal is the hard one. The correct semi-relaxed projection for equations (21)–(22), where the outer marginal Q1_r = a is hard and the inner marginal is soft, requires u ← a/(Kv) and v ← (b/K^T u)^{τ/(τ+γ^{−1})}; the printed updates are reversed, and Algorithm 7 is identical to Algorithm 2 despite being labeled as the opposite relaxation. Consequently, the calls in Algorithm 1 pass the marginals in the wrong order. Similarly, since T should be in Π_{gQ,gR} with row sums g_Q and column sums g_R, the call Sinkhorn(K_T, g_R, g_Q, δ) in Algorithms 1 and 4 swaps the two marginals, because Algorithm 5 returns row sums equal to its first argument. With these swaps, the iterates produced by the pseudocode do not satisfy P1_m = a and P^T1_n = b. The authors should correct the pseudocode and check that the released code matches the corrected version.","section":"Algorithms 1, 2, and 5"}],"minor_comments":[{"comment":"The displayed bound is typeset in an algebraically ambiguous way: D^2 L/N (α^2/2L) is not equal to 2D^2 L^2/(N α^2) as written; the intended expression appears to be D^2 L/(N α^2/(2L)). Please fix the notation.","section":"Proposition 3.3"},{"comment":"The proof contains an unresolved cross-reference: 'The proof of this for FRLC is given in ??' should refer explicitly to Proposition E.5.","section":"Proposition E.6"},{"comment":"Algorithm 2 and Algorithm 7 are identical even though one is called 'right marginal relaxed' and the other 'left marginal relaxed'; the labels or the updates should be corrected.","section":"Algorithms 2 and 7"},{"comment":"There are several typos, including 'straightfoward' in Section 1 and 'feasability' near the end of Section 3.2; these should be corrected in a final pass.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The core parameterization and algorithmic idea are sound and well-motivated, and the experimental scope is impressive. The main risks are the unproven δ lower bound in the convergence analysis and the swapped marginal arguments in the published pseudocode. Both are fixable within the manuscript's scope, so I do not recommend rejection, but the convergence guarantee and the algorithm specification need to be corrected before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core algorithmic idea is sound and the paper deserves a serious referee. What's new: applying the LC factorization of Lin et al. to the primal low-rank OT problem with general costs, and a coordinate mirror descent scheme that decouples into three OT subproblems, avoiding Dykstra projections entirely. The structural advantage is real: the alternating updates keep iterates feasible by construction, and the extension to unbalanced and semi-relaxed settings follows naturally from the same scheme. The empirical work is broad — synthetic benchmarks, graph clustering, spatial transcriptomics — and the shipped code makes the comparisons reproducible. The parameterization surjectivity and the equivalence between the LC objective and the low-rank problem are correct, and the initialization trick (full-rank random via Sinkhorn) is a small but useful contribution.\n\nThe soft spot is the convergence proof. Proposition E.5 claims a uniform lower bound δ on the inner marginals g_Q and g_R, which is needed for the block-smoothness constants and hence for the O(1/N) rate in Proposition 3.4. The argument asserts that large τ and O~(m²/ε) Sinkhorn iterations force ||g^(k) − g^(k−1)|| below ε, and that telescoping gives the δ bound. That does not follow. The τ penalty pulls the inner marginal toward the previous iterate, but the semi-relaxed projection is still an OT solve whose output marginal can have entries driven arbitrarily close to zero by the linear cost, regardless of τ. Pham et al. bounds the solver's distance to the fixed point, not the gap between that fixed point and the target b. So the δ-bound is not established, and the non-asymptotic rate is unsupported. This is a genuine gap, but it is localized: the feasibility claim, the no-Dykstra advantage, and the empirical comparisons stand on their own. The paper even acknowledges the criterion is weak, which is honest but doesn't fix the proof.\n\nMinor issue: the conclusion overstates the unbalanced FGW results slightly, since the gains there are smaller than in the Wasserstein case.\n\nBottom line: this is a worthwhile paper for the OT/ML audience. The convergence section needs a real fix — either a correct bound on the marginal gap, a weaker convergence statement, or an explicit caveat that the rate is empirical. With that, I'd support acceptance.","headline":"A genuinely useful low-rank OT algorithm with a real proof gap in its convergence guarantee; worth refereeing once the authors fix Proposition E.5.","tokens_in":49948,"tokens_out":1489,"would_cite":true,"duration_ms":18924,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["49Q22","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that low-rank optimal transport can be solved exactly by optimizing a latent-coupling factorization into three smaller OT problems, and gives an O(1/N) coordinate mirror-descent algorithm (FRLC) that stays feasible…","keywords":["low-rank optimal transport","latent coupling factorization","coordinate mirror descent","factor relaxation","Sinkhorn algorithm","Gromov-Wasserstein distance","unbalanced optimal transport","spatial transcriptomics"],"falsifier":"Run FRLC on a two-cluster cost matrix with a small penalty $\\tau$ and monitor the smallest entries of $g_Q$ and $g_R$: Proposition E.5 requires them to stay above the fixed floor $\\delta$ at every iteration. If some entry falls to zero while the iterates still converge, or if the convergence criterion $\\Delta_k$ does not shrink like $1/N$ at the claimed smoothness constant $L$, then the uniform-lower-bound premise that carries the proof is violated.","tokens_in":2245,"feed_emoji":"🚚","tokens_out":4617,"duration_ms":115879,"temperature":0.7,"pith_summary":"This paper claims that the low-rank optimal transport problem—finding a transport plan of rank at most $r$, with prescribed marginals, that minimizes a cost—can be reparameterized by a latent coupling (LC) factorization in which the plan is $P = Q\\,\\mathrm{diag}(1/g_Q)\\,T\\,\\mathrm{diag}(1/g_R)\\,R^T$, with $Q$ and $R$ matching the outer marginals and $T$ coupling two distinct inner marginals. Because the LC set surjects onto the set of rank-$r$ couplings, minimizing the cost over $(Q,R,T)$ is exactly the low-rank problem, not a proxy. On this parameterization the authors build FRLC, which alternates a factor-relaxation step (two independent semi-relaxed OT problems for $Q$ and $R$) with a balanced OT step for $T$, so each iteration is three Sinkhorn-type projections and the iterates stay feasible without Dykstra projections. They prove a non-asymptotic stationary convergence rate $O(1/N)$, and report lower primal costs than prior factored-coupling solvers on synthetic, graph-clustering, and spatial-transcriptomics tasks, while the latent coupling $T$ gives an interpretable cluster-level transport map.","feed_headline":"Low-rank transport splits into three smaller OT problems","feed_subtitle":"A latent-coupling factorization turns low-rank OT into three Sinkhorn problems, with lower cost on real and synthetic data.","key_machinery":"The machinery is the LC factorization $P = Q\\,\\mathrm{diag}(1/g_Q)\\,T\\,\\mathrm{diag}(1/g_R)\\,R^T$, whose key feature is two distinct inner marginals $g_Q$ and $g_R$ linked by a full coupling matrix $T$ rather than a shared diagonal $g$. The map from LC triples to couplings is surjective onto $\\Pi_{a,b}(r)$, so the three-factor objective is equivalent to low-rank OT. Around this identity the paper builds a block-coordinate mirror-descent loop: a factor-relaxation step fixes $T$ and solves independent semi-relaxed OT problems for $Q$ and $R$, with a KL penalty pulling their inner marginals toward the previous values, and a latent-coupling step fixes $Q,R$ and solves a balanced OT problem for $T$. Feasibility follows automatically because the $(Q,R)$ step enforces the outer marginals and the $T$ step enforces the inner marginals, so the algorithm never needs Dykstra projections; the $\\tau$ penalty supplies the smoothness constants used in the $O(1/N)$ convergence proof.","core_discovery":"The paper's central claim is that the latent coupling factorization $P = Q\\,\\mathrm{diag}(1/g_Q)\\,T\\,\\mathrm{diag}(1/g_R)\\,R^T$, where $g_Q = Q^T1_n$ and $g_R = R^T1_m$ are two separate inner marginals and $T$ is any coupling between them, parameterizes the set of rank-$r$ couplings $\\Pi_{a,b}(r)$ surjectively. Consequently the low-rank Wasserstein problem $\\min_{P\\in\\Pi_{a,b}(r)}\\langle C,P\\rangle$ is equivalent to minimizing $L_{LC}(Q,R,T)=\\langle C, Q\\,\\mathrm{diag}(1/g_Q)\\,T\\,\\mathrm{diag}(1/g_R)\\,R^T\\rangle$ over admissible triples. The authors exploit this equivalence to design FRLC, which performs coordinate mirror descent on the blocks $(Q,R)$ and $T$: the $(Q,R)$ block update relaxes the inner marginal constraints, decoupling into two semi-relaxed OT problems, while the $T$ update is a balanced OT problem; together these updates keep every iterate feasible without Dykstra projections. Under a $\\tau$-regularized inner-marginal penalty that enforces a uniform lower bound $\\delta$ on the entries of $g_Q$ and $g_R$, the objective is component-wise smooth and FRLC attains non-asymptotic stationary convergence $\\min_k \\Delta_k \\le 2D^2L^2/(N\\alpha^2)$, i.e. $O(1/N)$.","pith_inferences":["Editorial inference: because the LC parameterization is exactly equivalent to the rank-$r$ problem, the non-diagonal latent coupling $T$ is the structural novelty relative to diagonal factored-coupling solvers; a controlled comparison that diagonalizes FRLC's output would isolate how much of the empirical improvement comes from $T$ versus the coordinate split.","Editorial inference: the convergence guarantee depends on the $\\tau$ penalty keeping inner marginals bounded away from zero, so a testable robustness criterion is to measure the empirical stationarity gap as $\\tau$ is reduced on a fixed dataset; performance should degrade gracefully until the proof's regime ends.","Editorial inference: the two distinct inner marginals make the LC factorization a natural tool for comparing datasets with different numbers of latent clusters; the paper's non-square example suggests that the learned $T$ estimates a coarse-grained transition between clusters, which could be validated against the coarse-grained full-rank optimal plan when the Monge map is known."],"forward_implications":["Because $LC_{a,b}(r)$ surjects onto $\\Pi_{a,b}(r)$, any feasible rank-$r$ coupling has an LC representation, so minimizing $L_{LC}$ is exactly the low-rank OT problem and introduces no additional proxy error.","FRLC splits each iteration into two semi-relaxed OT problems and one balanced OT problem, all solved with Sinkhorn, and iterates remain in the constraint set without Dykstra projections.","With the $\\tau$ penalty enforcing a uniform lower bound on inner-marginal entries, the FRLC objective is component-wise smooth and the algorithm attains $\\min_k \\Delta_k = O(1/N)$ in the stationarity criterion.","The same framework extends to Wasserstein, Gromov-Wasserstein, and fused Gromov-Wasserstein objectives under balanced, unbalanced, or semi-relaxed marginal constraints, with storage linear in the data size for fixed rank.","On synthetic mixtures, graph partitioning, and mouse-embryo spatial transcriptomics, FRLC reaches lower primal cost or better downstream alignment metrics than the factored-coupling solvers it compares with, while its non-diagonal latent coupling $T$ gives a cluster-level interpretation."],"supporting_citations":[{"why":"Introduced factored couplings through hubs for the k-Wasserstein barycenter problem, the ancestor of the low-rank coupling parameterization.","marker":"Forrow et al. (2019)"},{"why":"Adapted factored couplings to the primal low-rank OT problem and supplied the mirror-descent framework that FRLC builds on.","marker":"Scetbon et al. (2021)"},{"why":"Introduced the latent coupling factorization with two inner marginals that FRLC optimizes.","marker":"Lin et al. (2021)"},{"why":"Establishes that every rank-$r$ nonnegative matrix has a factored coupling decomposition, the surjectivity fact the LC parameterization inherits.","marker":"Cohen & Rothblum (1993)"},{"why":"Provides the Sinkhorn algorithm used as the subroutine for all three OT steps in FRLC.","marker":"Cuturi (2013b)"},{"why":"Supplies the block-descent lemma that yields the $O(1/N)$ coordinate mirror-descent convergence rate.","marker":"Beck & Tetruashvili (2013)"},{"why":"Supplies the non-asymptotic stationarity criterion and the mirror-descent template extended to the block-coordinate setting.","marker":"Ghadimi et al. (2014)"},{"why":"Provides the convergence bound for semi-relaxed projections used to justify the uniform lower bound on inner-marginal entries in the smoothness proof.","marker":"Pham et al. (2020)"}],"fun_headline_variants":["Low-rank OT splits into three Sinkhorn blocks","Latent coupling reduces low-rank OT to three OT subproblems","Three OT problems: latent coupling for low-rank transport","Coordinate mirror descent for low-rank OT via latent coupling","Latent coupling decomposes low-rank OT into three OT pieces"],"cache_read_input_tokens":52096,"weakest_assumption_plain":"The convergence proof rests on assuming that a tunable penalty $\\tau$ keeps every entry of the two inner marginals (the column sums of $Q$ and the column sums of $R$) bounded away from zero throughout all iterations; if that lower bound is not actually delivered, the smoothness lemma and the $O(1/N)$ rate do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Low-rank OT splits into three Sinkhorn blocks","Latent coupling reduces low-rank OT to three OT subproblems","Three OT problems: latent coupling for low-rank transport","Coordinate mirror descent for low-rank OT via latent coupling","Latent coupling decomposes low-rank OT into three OT pieces"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001108,"raw_usage":{"total_tokens":4715,"prompt_tokens":1141,"completion_tokens":3574,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":757,"completion_tokens_details":{"reasoning_tokens":3494}},"tokens_in":757,"tokens_out":3574,"duration_ms":23809,"temperature":1.0,"reasoning_tokens":3494,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T19:34:56.156430+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run FRLC on a two-cluster cost matrix with a small penalty $\\tau$ and monitor the smallest entries of $g_Q$ and $g_R$: Proposition E.5 requires them to stay above the fixed floor $\\delta$ at every iteration. If some entry falls to zero while the iterates still converge, or if the convergence criterion $\\Delta_k$ does not shrink like $1/N$ at the claimed smoothness constant $L$, then the uniform-lower-bound premise that carries the proof is violated.","supporting_citations":[{"cited_title":"Statistical O ptimal T ransport via F actored C ouplings","cited_arxiv_id":null,"evidence_quote":"Introduced factored couplings through hubs for the k-Wasserstein barycenter problem, the ancestor of the low-rank coupling parameterization."},{"cited_title":"Low- R ank S inkhorn F actorization","cited_arxiv_id":null,"evidence_quote":"Adapted factored couplings to the primal low-rank OT problem and supplied the mirror-descent framework that FRLC builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduced the latent coupling factorization with two inner marginals that FRLC optimizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes that every rank-$r$ nonnegative matrix has a factored coupling decomposition, the surjectivity fact the LC parameterization inherits."},{"cited_title":"and Tetruashvili, L","cited_arxiv_id":null,"evidence_quote":"Supplies the block-descent lemma that yields the $O(1/N)$ coordinate mirror-descent convergence rate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the convergence bound for semi-relaxed projections used to justify the uniform lower bound on inner-marginal entries in the smoothness proof."}],"review_version":1}