Condition-Number-Robust Low-Rank Matrix Completion

Research-attempt provenance

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

The rank of a matrix is the dimension of its column space. Matrix completion reconstructs a low-rank matrix from a subset of its entries; matrix sensing reconstructs it from specified linear measurements. Tensor decomposition represents a multiway array as a sum of simple outer products.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. Source-record limitation: The target is matching unspecified empirical behavior; no sampling distribution, recovery condition, algorithm or condition-number bound is fixed.

Statement recorded in the supplied source.

Derive recovery guarantees for factorization-based low-rank matrix-completion algorithms whose dependence on matrix condition numbers matches their empirical performance. [S2]

Source status.

The supplied catalogue labels this source record partially solved; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

The source asks about condition-Number-Robust Low-Rank Matrix Completion.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30005134 (OWR-10252933-001). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Re-thinking High-dimensional Mathematical Statistics $2023$, Oberwolfach Reports, DOI 10.4171/owr/2022/25, pp. 1377--1430 https://doi.org/10.4171/owr/2022/25.
• S3 Zilber--Nadler, matrix completion https://doi.org/10.1137/21M1433812.
• S4 Inductive matrix completion https://proceedings.mlr.press/v162/zilber22a.html.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Preparation and review.

The original source and UnsolvedMath contributors retain attribution for the source extract. Codex (GPT-6; exact serving revision not exposed) assisted with definitions, English summaries, scope notes and formatting. No new human mathematical authorship or independently verified solution is asserted. Permanent source ID 30005134 and code OWR-10252933-001 checked against the complete supplied registry and current repository. Distinct upstream records, including repeated questions and broad or damaged extracts, are retained for complete coverage of the source CS category. A repeated record is not a new independent conjecture. Complete mathematical-equivalence and current-literature review has not been performed. Preparation and final review follow contribution prompts C and D, with source gaps disclosed. Structural and rendering checks do not establish a new theorem or open status.

Literature and context check

I read Nadler's GNMR talk on pages 1383--1384 of the primary report and the Zilber--Nadler ICML paper's official abstract. The report explicitly distinguishes quadratic local convergence from the condition-number dependence in recovery conditions. The abstract concerns inductive completion and does not by itself supply a condition-number-free theorem for ordinary completion. The following fully observed diagonal calculation is a controlled auxiliary case; it isolates one source of conditioning but does not replace random entry sampling.

Research attempt: Balanced-factor conditioning and a relative Newton calculation

Where a factor gradient iteration retains the condition number.

Let $\lambda_1,\ldots,\lambda_r>0$, $r\geq1$, and consider \[ F(u,v)=\frac12\sum_{i=1}^r(u_iv_i-\lambda_i)^2. \] This is the diagonal fully observed factorization problem. Gradient descent preserves the subspace $u=v=a$ and on it has iteration \[ a_i^+=a_i-\eta(a_i^2-\lambda_i)a_i. \] At the positive solution $a_i=\sqrt{\lambda_i}$, the derivative of this update is $1-2\eta\lambda_i$. Write $L=\max\lambda_i$, $\mu=\min\lambda_i$, and $\kappa=L/\mu$. Any fixed step size has worst linearized absolute factor at least \[ \max\{|1-2\eta\mu|,|1-2\eta L|\} \geq \frac{L-\mu}{L+\mu}. \] For proof, if both absolute values were smaller than a number $\rho$, then $\eta>(1-\rho)/(2\mu)$ and $\eta<(1+\rho)/(2L)$. These inequalities require $\rho>(L-\mu)/(L+\mu)$. Equality is attained at $\eta=1/(L+\mu)$, and all intermediate eigenvalues have absolute factor at most the endpoint maximum because an affine function on an interval has its maximal absolute value at an endpoint. Thus for large $\kappa$ even the best fixed scalar step has local factor $(\kappa-1)/(\kappa+1)$, approaching one. This statement concerns the linearization of this specified gradient method, not all factorization methods.

A normalization that removes that factor in this toy model.

For positive $a_i$ instead use the scalar Newton step \[ a_i^+=\frac12\left(a_i+\frac{\lambda_i}{a_i}\right). \] Let $r_i=(a_i-\sqrt{\lambda_i})/\sqrt{\lambda_i}$. Exact algebra gives \[ r_i^+=\frac{r_i^2}{2(1+r_i)}. \] If $|r_i|\leq1/2$, then $0\leq r_i^+\leq r_i^2\leq1/4$; by induction the relative errors converge quadratically, with a constant independent of $\kappa$. This route succeeds only in a relative neighborhood: the initial absolute error allowed in the smallest component is proportional to $\sqrt\mu$. The update also divides by $a_i$, so it is undefined at zero. For a perturbed datum $\lambda_i+e_i$, the limiting positive root, when it exists, obeys \[ \frac{\sqrt{\lambda_i+e_i}-\sqrt{\lambda_i}}{\sqrt{\lambda_i}} =\frac{e_i/\lambda_i}{\sqrt{1+e_i/\lambda_i}+1}. \] Thus absolute data noise has relative scale $e_i/\lambda_i$, and the condition-number issue has not vanished from initialization or stability.

The sampling obstruction cannot be removed by rescaling factors.

Suppose only the two diagonal entries of \[ X_t=\begin{pmatrix}1&t\\t^{-1}&1\end{pmatrix},\qquad t>0, \] are observed. Every $X_t$ has rank one: its second row equals $t^{-1}$ times its first. Its condition number restricted to nonzero singular values is therefore one. Yet all these different matrices produce the same observations. No algorithm can recover all of them from those observations, regardless of factor normalization or local convergence rate. A full recovery theorem must control sampling identifiability, for example through a suitable injectivity condition on the relevant matrix differences; the relative Newton calculation does not establish that condition.

Verification and adversarial audit

The gradient-rate statement is explicitly a local derivative bound on the balanced diagonal invariant subspace. At $\kappa=1$ its optimal factor is zero, as the formula predicts; it is not asserted as a nonzero lower bound then. Newton's relative identity is exact and includes its positive-denominator hypothesis. The indistinguishable sampled matrices have rank exactly one for every $t>0$, so their nonzero-singular-value condition number really is one.

Audit corrections.

Separated convergence rate from the relative size of its basin and from statistical identifiability. The failure example uses the condition number over nonzero singular values, avoiding an artificial infinite condition number for a rank-one matrix.

External computation.

None; symbolic arguments and boundary checks only.

Scope and remaining gaps

The route explains how local rescaling can improve a specific factor update, and why that alone cannot prove the source's recovery guarantee. It supplies no incoherent random-sampling theorem, GNMR initialization guarantee, or sharp sample complexity matching empirical condition-number behavior. All target recovery questions remain unresolved by this auxiliary calculation.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The calculations below the preserved source statement investigate a concrete route, but establish no substantiated new progress toward the entire original target. Known special cases and failed sufficient conditions are not credited as a solution.

References

The original source references and catalogue attribution are preserved in the Sources section above. The following URLs were actually consulted for this attempt; retention of an additional original reference does not claim fresh consultation of it.

• https://ems.press/content/serial-article-files/46963 (consulted 2026-10-11).
• https://proceedings.mlr.press/v162/zilber22a.html (consulted 2026-10-11).

Model and contributor disclosure

Codex GPT-6 completed written-proof review of this attempt at its declared scope; this is model-assisted review, not independent human proof checking. OpenAI gpt-6-astra, requested reasoning configuration ultra, generated this research attempt on 2026-10-11. The exact serving revision is not exposed. Codex GPT-6 performed orchestration and repository-format review; its exact serving revision is also not exposed. The mathematical route, boundary checks and final adversarial self-audit followed contribution prompts A then B in docs/contribution_prompts.md, after reading CONTRIBUTING.md. Python 3.14.2 assembled the standalone documents; any mathematical computation is specified in Verification. No theorem prover was used. No human mathematical authorship, substantial human proof correction, or independent human proof checking is asserted. Model-assisted review, source retrieval, and structural checks do not establish correctness or novelty. Full private reasoning transcripts are unavailable as reproducibility artifacts; the complete arguments, inputs and outcomes actually used are stated here or in the companion batch audit.

Final status

Unresolved as a new research contribution. This is a concrete route investigation, not a claim of new complete resolution or a current-status certification. A known answer reproduced for context does not become a new contribution. The catalogue's source-status label is preserved; this attempt status does not assert that a source-labelled solved question is open.