{"id":"1f544d35-8b65-4923-acaa-14d52cbc6f13","arxiv_id":"2608.07413","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The discrete movable-antenna position selection problem for MI maximization is shown to be monotone submodular under a minimum-spacing constraint, and a greedy algorithm achieves a 1/3 approximation in polynomial time.","lead":"This paper designs a fast greedy algorithm for choosing discrete movable-antenna positions in an uplink multi-user MIMO system, maximizing mutual information with a theoretical guarantee of at least one third of the optimal value. It also extends the design to imperfect channel knowledge, and reports near-optimal performance with about 34 times lower runtime than branch-and-bound.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1/3 guarantee for P3 lacks proof that the exact-cardinality feasible family is a 2-system; Lemma 3 only covers the spacing-only system.","rationale":"The reader's strongest_claim and rationale identify the same missing link: the 1/3 guarantee is stated for the cardinality-constrained problem P3 without proving the capped feasible family is a 2-system. This is indeed the most load-bearing concern because the 1/3 ratio is the paper's headline theoretical contribution. I agree with the reader's CONDITIONAL verdict: the gap is correctable (the truncation of a 2-system at rank N_BS is a 2-system, and monotonicity makes the equality constraint harmless), but the paper should state and prove this explicitly. I do not fully agree with the reader's weakest_assumption phrasing, which emphasizes the per-position channel independence (no mutual coupling) as the primary risk; that is a modeling assumption rather than an internal proof gap. The capped-2-system issue is more central to the mathematical claim as written. The imperfect-CSI covariance dimensional inconsistency (defining Ψ over N_BS antennas while S ranges over N_S candidate positions) is a real flaw in the robust extension, but it does not threaten the perfect-CSI central claim. The algorithm's feasibility check in Algorithm 1 also appears to reject equality (line 8 uses ≤ N_D instead of < N_D), a separate typo-level bug that should be corrected but does not undermine the theoretical framework. Overall, the reader's cautious CONDITIONAL verdict is appropriate: the paper's core submodularity analysis is sound, but the 2-system proof for the exact-cardinality family must be added and the robust formulation clarified before the claims can be accepted without qualification.","tokens_in":22427,"tokens_out":25400,"duration_ms":203947,"concrete_test":"Verify analytically or by exhaustive enumeration that (W, I_NBS) is a 2-system. Analytical route: adapt the proof of Lemma 3; for any A ⊆ W and any maximal sets J (smallest) and I (largest) in I_NBS, show |I| ≤ 2|J| by splitting into cases |J| < N_BS (then J is maximal in the spacing-only system and the neighborhood-union argument applies) and |J| = N_BS (then either |I| = N_BS or |I| is a spacing-only maximal set, giving |I| ≥ N_BS/2 via Lemma 3). Numerical route: exhaustively enumerate all subsets for small parameters (e.g., N_S = 10, N_D = 2, N_BS = 2,3,4), compute the rank quotient max|M|/min|M| over all maximal capped sets in each A ⊆ W, and confirm the maximum is ≤ 2.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that P3 is monotone submodular maximization subject to a 2-system constraint, so greedy DCSPS attains 1/3 of the optimum. Lemma 3 proves that the spacing-only independence system I = {S ⊆ W : |i-j| ≥ N_D ∀i,j ∈ S} is a 2-system. However, P3 imposes the additional exact-cardinality constraint |S| = N_BS (C2). The paper never proves that the capped family I_NBS = {S ∈ I : |S| = N_BS} is a 2-system, nor does it invoke the standard truncation argument. Without this step, the greedy guarantee 1/(1+k) is not directly applicable to P3: the 1/3 bound would nominally hold for the spacing-only system, whose optimal value can exceed the cardinality-constrained optimum. The gap is fixable—the truncation of a k-system at rank r remains a k-system, and monotonicity of c(S) makes |S| = N_BS equivalent to |S| ≤ N_BS for optimality—but the paper omits this reasoning. If the capped family were not a 2-system, the 1/3 approximation claim would collapse, making this the load-bearing link in the proof chain.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers discrete movable-antenna (MA) position design at the base station of an uplink multi-user MIMO system. It formulates a mutual-information (MI) maximization problem over a finite set of candidate positions, subject to a minimum-spacing constraint and the exact selection of N_BS positions. The authors prove that the MI objective is monotone submodular (Lemma 2), show that the spacing-only feasible family is a 2-system (Lemma 3), and propose a greedy algorithm (DCSPS) with a claimed 1/3-approximation guarantee. They then extend the framework to imperfect CSI by replacing the expected MI with a deterministic Jensen surrogate, yielding an R-DCSPS algorithm with the same nominal guarantee for the surrogate objective. Numerical experiments compare the proposed schemes against branch-and-bound, channel-gain greedy, equidistant, random, and fixed-antenna baselines, reporting near-optimal MI and orders-of-magnitude runtime reductions.","tokens_in":22646,"tokens_out":12102,"duration_ms":104800,"significance":"If the 1/3 approximation claim is fully established, this is a significant contribution to the discrete-MA literature: it provides a polynomial-time design algorithm with a formal worst-case guarantee, a clean submodularity proof, and an extensive numerical study. The paper's treatment of imperfect CSI via a closed-form surrogate and the 'virtual user' interpretation of estimation error are also interesting and go beyond the commonly used exhaustive-search baselines. The paper is carefully written and the simulation suite is broad, including complexity scaling, aperture effects, and practical transceiver comparisons.","major_comments":[{"comment":"The claimed 1/3 guarantee for problem P3 is not fully proved. Lemma 3 establishes that the spacing-only independence system I = {S ⊆ W : |i−j| ≥ N_D for all i,j ∈ S} is a 2-system, but P3 additionally imposes the exact-cardinality constraint |S| = N_BS. The paper never proves that the capped family I_{≤N_BS} = {S ∈ I : |S| ≤ N_BS} is a 2-system, nor does it explain how the cardinality constraint interacts with the k-system greedy theorem. The gap is repairable: the truncation of a k-system at rank r is again a k-system, and the greedy guarantee against the relaxed problem (with |S| ≤ N_BS) implies the same guarantee against the exact-cardinality optimum because the relaxed optimum upper-bounds the constrained optimum. However, the paper should state this argument explicitly; as written, the statement 'the design problem falls into the category of monotone submodular maximization subject to a 2-system constraint' is not directly justified for the exact-cardinality problem since the exact-cardinality family is not hereditary.","section":"Sec. IV, Lemma 3 and problem P3"},{"comment":"The validity check in Algorithm 1 rejects a candidate position j when min_{s∈S} |s−j| ≤ N_D, which enforces the strict inequality |s−j| > N_D. The constraint C3 of P3 requires |s−j| ≥ N_D, so positions at exactly distance N_D are feasible but are excluded by the algorithm. This means the algorithm searches over a strictly smaller feasible family than the one for which the 2-system and the greedy guarantee are established. The condition should be '< N_D' (or equivalently reject only when min |s−j| < N_D) to match the problem definition.","section":"Algorithm 1, line 8"},{"comment":"The robust surrogate c_r(S) is claimed to be monotone submodular 'based on our derivation in Sec. IV', but the paper does not explicitly define the per-position channel vectors for the virtual channel ~H_S. To apply Lemma 1 and Lemma 2 one needs to write c_r(S) = log2 det(I + ρ Σ_{u∈S} ~w(u)~w(u)^H) with fixed vectors ~w(u) in dimension N_BS+KN_U, and then note that the positivity and rank-one update arguments carry over unchanged. This step is a short derivation, but it should be included because the reader cannot otherwise verify that the monotone submodularity of the surrogate is truly inherited from Sec. IV despite the enlarged column dimension.","section":"Sec. V, Eq. (49)-Eq. (51)"}],"minor_comments":[{"comment":"The displayed equality |I| = Σ_{x∈J} |I ∩ B_x| is not justified because the neighborhoods B_x may overlap; the correct statement is an inequality |I| ≤ Σ_{x∈J} |I ∩ B_x|. The subsequent bound |I| ≤ 2|J| remains valid, so the lemma's conclusion is unaffected.","section":"Lemma 3 proof"},{"comment":"The definition of a k-system uses both S and A for the subset in condition 3; this is confusing. Please use a single symbol, e.g., 'for any subset S ⊆ V' throughout.","section":"Definition 3"},{"comment":"Reference [30] (Petersen, 'A stabilization algorithm for a class of uncertain linear systems') does not appear related to submodularity or to the definition of submodular functions. Please check the citation and replace it with a standard submodularity reference.","section":"Reference [30]"},{"comment":"The complexity claim O(N_S N_BS^4) is plausible but not derived. Since the determinant update in Algorithm 1 may be implemented with a rank-one matrix determinant lemma, the per-evaluation cost should be O(N_BS^2) or O(N_BS^3) depending on the implementation; a short derivation of the stated exponent would improve the paper.","section":"Sec. IV-D complexity analysis"},{"comment":"The phrase 'achieve at least 90% of the optimal solution's MI gain' can be read as 90% of the absolute MI. The numerical evidence supports it for the MI gain over the fixed half-wavelength benchmark (e.g., Fig. 7: DCSPS gain 3.280 bits/s/Hz vs BnB gain 3.517 bits/s/Hz, about 93%). Please clarify in the text or captions that the 90% refers to the gain over the benchmark, not the absolute MI.","section":"Abstract and Sec. VI"},{"comment":"The virtual channel matrix ~H_S is defined as [E_S, Yhat H_S], but it is not stated that its column dimension is N_BS + K N_U and that this dimension is independent of S. This observation is needed for the submodularity argument.","section":"Sec. V-B, Eq. (51)"}],"recommendation":"major_revision","confidential_remarks":"The paper is well-executed overall, and the central submodularity proof (Lemma 2) is clean. The main concern is the gap between Lemma 3 and the exact-cardinality problem P3, which concerns the 1/3 guarantee; this is repairable with a short truncation argument. The strict-inequality bug in Algorithm 1 is also easy to fix. I do not see an unfixable flaw, and the numerical contribution is solid. I recommend major revision with a request to close the proof gap and correct the algorithm before it can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Plain take: this is a useful, mostly correct paper. The genuinely new piece is the observation that the minimum-spacing constraint defines a 2-system, so the standard greedy theorem gives a 1/3 approximation for discrete MA placement. That's a nice result for a problem where everyone else is doing BnB or enumeration. The robust extension via Jensen's surrogate is also new and sensible, and the simulation study is thorough: the DCSPS tracks BnB within a few tenths of a bit, it scales to 32 antennas while BnB dies at 4, and the runtime numbers (34.4x) are believable.\n\nWhere it's soft: the paper states the 1/3 guarantee for P3, which has the exact cardinality constraint |S|=N_BS, but Lemma 3 only proves the spacing-only independence system is a 2-system. The fix is the standard truncation argument: I_r = {S in I: |S| <= r} is still a 2-system, and since c(S) is monotone, the optimum over I_r equals the optimum over exact cardinality. The greedy algorithm runs exactly r steps, so the guarantee applies. The paper should write this down; right now the chain has a missing link. Relatedly, the submodularity of the robust surrogate c_r(S) is asserted rather than shown. It does go through—each position contributes a fixed vector [e_u; w(u)]—but the authors should prove it explicitly rather than pointing at Sec. IV. Minor wording issues: 'orders-of-magnitude' is a stretch for 34.4x, and the 90% number is empirical, not a guarantee, so it should be labeled as such.\n\nI don't share the stress-test's worry that the cardinality cap could break the 2-system property; truncation preserves it. I also didn't find the dimensional inconsistency in the error covariance model that the reader's report mentions—Psi_S = E_S E_S^H works out. Worth double-checking, but not a blocker.\n\nWho is this for? The MA/fluid-antenna community and anyone doing combinatorial antenna selection under geometric constraints. They'll cite it. It deserves a serious referee; I'd accept it given minor revision.","headline":"A mostly sound submodularity framework for discrete MA placement; the 1/3 guarantee is real but the paper should explicitly handle the cardinality constraint.","tokens_in":23220,"tokens_out":4987,"would_cite":true,"duration_ms":40288,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Discrete movable-antenna placement is submodular; greedy search carries a 1/3 guarantee.","keywords":["movable antennas","discrete position design","mutual information maximization","submodular optimization","2-system constraint","greedy algorithm","robust design","MU-MIMO uplink"],"falsifier":"Enumerate every feasible position set for a small instance (e.g., $N_{BS}=4$, $N_S=30$) and compare the DCSPS output with the true optimum: any ratio below $1/3$ disproves the guarantee. Equivalently, run a full-wave simulation of two antennas at spacing $N_D$ and check whether the incremental MI gain of adding a slot to a larger nested set ever exceeds the gain for a smaller set, which would violate submodularity.","tokens_in":22200,"feed_emoji":"📡","tokens_out":9203,"duration_ms":74452,"temperature":0.7,"pith_summary":"The paper asks where to place a handful of movable antennas at a base station among a discrete grid of candidate slots, with the goal of maximizing the mutual information of the uplink multi-user MIMO channel. It establishes that this placement problem is a monotone submodular maximization under a 2-system constraint, so the natural greedy rule—each step add the feasible slot with the largest incremental MI gain while keeping a minimum spacing between antennas—is guaranteed to deliver at least one-third of the optimal MI. The argument is carried by a codebook channel model in which each slot's response is fixed and the selected channel is simply the corresponding columns of a precomputed matrix. The same framework is extended to imperfect channel knowledge by maximizing a Jensen-based surrogate that keeps submodularity and the one-third guarantee. If the claim holds, an NP-hard combinatorial antenna placement becomes a polynomial-time design with a formal worst-case bound and near-optimal performance in simulations.","feed_headline":"Greedy rule reaches one-third of the optimal MI for movable antennas","feed_subtitle":"Polynomial-time search runs 34.4 times faster than branch-and-bound while keeping near-optimal mutual information.","key_machinery":"The load-bearing object is the incremental-gain formula $\\Delta(v|S)=\\log_2\\left(1+\\rho w(v)^H A_S w(v)\\right)$, with $A_S=\\left(I_{KN_U}+\\rho \\sum_{u\\in S} w(u)w(u)^H\\right)^{-1}$, where $w(v)=G^H\\Sigma^H f(v)$ is the fixed channel response of candidate slot $v$. This formula makes MI gains additive through rank-one updates, and since adding a slot shrinks $A_S$ in the Lowner order, incremental gains decrease with larger sets—diminishing returns, i.e., submodularity. The 2-system is the independence family of slot sets with pairwise spacing at least $N_D$; the proof that any two maximal independent sets in a subset differ by at most a factor of two uses the fact that each selected slot's radius-$N_D$ neighborhood can contain at most two points of another valid placement. The greedy algorithm maximizes $\\Delta(v|S)$ over feasible remaining slots at each step.","core_discovery":"Central claim: with perfect CSI, the mutual information $c(S)=\\log_2\\det\\left(I_{|S|}+\\rho H_S H_S^H\\right)$ is a monotone submodular set function over candidate slots, and the family of position sets satisfying the minimum-spacing constraint $|i-j|\\ge N_D$ is a 2-system. Therefore the distance-constrained submodular position search (DCSPS) greedy algorithm achieves at least $1/3$ of the optimal MI. With imperfect CSI, the expected-MI objective is replaced by a deterministic Jensen surrogate $c_r(S)=\\log_2\\det\\left(I_{|S|}+\\rho \\tilde{H}_S \\tilde{H}_S^H\\right)$, where $\\tilde{H}_S=[E_S,\\hat{H}_S]$ appends the square root of the estimation-error covariance as virtual columns; this surrogate is still monotone submodular, so the robust DCSPS preserves the $1/3$ bound for the surrogate. The paper further reports that DCSPS reaches at least 90% of the optimal MI gain in simulations at polynomial complexity, running 34.4 times faster than branch-and-bound.","pith_inferences":["If residual mutual coupling at the minimum spacing is non-negligible, the fixed-slot response assumption fails; an immediate test is to recompute the embedded element patterns with neighboring antennas present and check whether the diminishing-returns inequality still holds.","The virtual-user view of channel estimation error suggests a design rule: the number of virtual columns equals $N_{BS}$, so error-aware placement should reserve spatial dimensions for estimation uncertainty; this could be tested by comparing R-DCSPS with a scheme that optimizes the number of active streams.","The $1/3$ bound is worst-case; if a planar-array extension keeps the independence system a bounded $k$-system, the same submodular machinery could support tighter guarantees via curvature."],"forward_implications":["DCSPS returns a position set whose MI is at least $1/3$ of the optimum with complexity $O(N_S N_{BS}^4)$, replacing exponential branch-and-bound.","In imperfect-CSI settings, R-DCSPS retains the same guarantee for the surrogate objective while needing no Monte Carlo averaging per candidate.","The Jensen surrogate's virtual-channel interpretation says estimation error consumes $N_{BS}$ spatial degrees of freedom as virtual users, so the MI loss from imperfect CSI is structural rather than a numerical artifact.","Aperture expansion matters more than increasing the number of grid slots for MI gains; the gain saturates at the continuous-MA upper bound.","The MI-based greedy criterion outperforms channel-gain greedy, random feasible placement, and equidistant placement, so spatial-DoF projection, not aperture alone, is the source of the gain."],"supporting_citations":[{"why":"Supplies the MA-MIMO field-response channel model and per-position response $w(v)$ that the codebook reformulation relies on.","marker":"[14]"},{"why":"Gives the branch-and-bound discrete MA placement baseline that the paper uses as the optimal-MI upper bound and complexity comparison.","marker":"[22]"},{"why":"Precedent that MI maximization via antenna selection is submodular in multiuser MIMO, the property the paper extends to discrete MA placement.","marker":"[28]"},{"why":"States the $1/(1+k)$ approximation guarantee for monotone submodular maximization under a $k$-system, which yields the $1/3$ bound with $k=2$.","marker":"[32]"},{"why":"Cited as the guarantee that a greedy algorithm attains $1-1/e$ of optimal for monotone submodular objectives with cardinality constraints, the starting point for the constrained result.","marker":"[34]"},{"why":"Supplies the additive statistical channel estimation error model and the expected-MI formulation used in the robust design.","marker":"[35]"},{"why":"Provides the specific branch-and-bound scheme used as the optimal MI baseline in the numerical comparison.","marker":"[37]"}],"fun_headline_variants":["Submodular greedy for movable antennas: 1/3 optimal, 34x faster","Low-complexity MA placement: submodular, robust, near-optimal MI","Movable antenna design: 90% optimal MI with polynomial complexity","Greedy submodular search yields 1/3 optimal MI for MAs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that each candidate slot's channel response $w(v)$ is fixed regardless of which other slots are selected—the minimum-spacing constraint is taken to eliminate mutual coupling—so if residual electromagnetic coupling at the chosen spacing changes an antenna's response when a neighbor moves, the codebook model $H_S=\\bar{F}_S^H\\Sigma G$ and the submodularity proof collapse.","fun_headline_variants_meta":{"raw":{"variants":["Submodular greedy for movable antennas: 1/3 optimal, 34x faster","Low-complexity MA placement: submodular, robust, near-optimal MI","Movable antenna design: 90% optimal MI with polynomial complexity","Greedy submodular search yields 1/3 optimal MI for MAs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00078,"raw_usage":{"total_tokens":3501,"prompt_tokens":1053,"completion_tokens":2448,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":669,"completion_tokens_details":{"reasoning_tokens":2360}},"tokens_in":669,"tokens_out":2448,"duration_ms":15063,"temperature":1.0,"reasoning_tokens":2360,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:29:42.007859+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate every feasible position set for a small instance (e.g., $N_{BS}=4$, $N_S=30$) and compare the DCSPS output with the true optimum: any ratio below $1/3$ disproves the guarantee. Equivalently, run a full-wave simulation of two antennas at spacing $N_D$ and check whether the incremental MI gain of adding a slot to a larger nested set ever exceeds the gain for a smaller set, which would violate submodularity.","supporting_citations":[{"cited_title":"A simple and effective approach for transmit antenna selection in multiuser massive MIMO leveraging submodularity,","cited_arxiv_id":null,"evidence_quote":"Precedent that MI maximization via antenna selection is submodular in multiuser MIMO, the property the paper extends to discrete MA placement."},{"cited_title":"Improved approxi- mations for k-exchange systems,","cited_arxiv_id":null,"evidence_quote":"States the $1/(1+k)$ approximation guarantee for monotone submodular maximization under a $k$-system, which yields the $1/3$ bound with $k=2$."},{"cited_title":"Optimal approximation for submodular and supermodular optimization with bounded curvature,","cited_arxiv_id":null,"evidence_quote":"Cited as the guarantee that a greedy algorithm attains $1-1/e$ of optimal for monotone submodular objectives with cardinality constraints, the starting point for the constrained result."},{"cited_title":"A framework of robust transmission design for IRS-aided MISO communications with imperfect cascaded channels,","cited_arxiv_id":null,"evidence_quote":"Supplies the additive statistical channel estimation error model and the expected-MI formulation used in the robust design."},{"cited_title":"Exploiting movable antennas in multicast communications,","cited_arxiv_id":null,"evidence_quote":"Provides the specific branch-and-bound scheme used as the optimal MI baseline in the numerical comparison."}],"review_version":1}