Pith Number

pith:KVIQTO6G

pith:2026:KVIQTO6GC6PVZVDXZQMFBVGRPV

not attested not anchored not stored refs resolved

Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers

Arnaud Vandaele, Nicolas Gillis, Timothy Baeckelant

Non-convex optimization solvers compute four classical lower bounds on the nonnegative rank of matrices, including the first method for the self-scaled bound.

arxiv:2605.14058 v1 · 2026-05-13 · math.OC · cs.DM

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{KVIQTO6GC6PVZVDXZQMFBVGRPV}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

our algorithm for computing the SSB is the first available in the literature, to the best of our knowledge. It allows us to improve the best known lower bound on the nonnegative rank for some matrices. In some cases, they coincide with the best known upper bound, thereby establishing their exact nonnegative rank for the first time.

C2weakest assumption

That non-convex solvers reliably reach solutions accurate enough to certify valid lower bounds without getting stuck in poor local minima that would invalidate the bound.

C3one line summary

Non-convex solvers compute improved lower bounds on nonnegative matrix rank, with a new algorithm for the self-scaled bound that establishes exact rank for some matrices.

References

33 extracted · 33 resolved · 1 Pith anchors

[1] G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. L. Hammer, and B. Simeone. Consensus algorithms for the generation of all maximal bicliques.Discrete Applied Mathematics, 145(1):11–21, 2004 2004

[2] S. Arora, R. Ge, R. Kannan, and A. Moitra. Computing a nonnegative matrix factorization–provably. InACM Symposium on Theory of Computing, pages 145–162, 2012 2012

[3] C. Barefoot, K. A. Hefner, K. F. Jones, and J. R. Lundgren. Biclique covers of the complements of cycles and paths in a digraph.Congressus Numerantium, 53:133–146, 1986 1986

[4] L. Beasley and T. Laffey. Real rank versus nonnegative rank.Linear Algebra and Its Applications, 431(12):2330–2335, 2009 2009

[5] A. Ben-Tal and A. Nemirovski. On polyhedral approximations of the second-order cone.Mathematics of Operations Research, 26(2):193–205, 2001 2001

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-05-17T23:39:12.558120Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

555109bbc6179f5cd477cc1850d4d17d75f7a1c411c8f577125b4c0c4a2143c6

Aliases

arxiv: 2605.14058 · arxiv_version: 2605.14058v1 · doi: 10.48550/arxiv.2605.14058 · pith_short_12: KVIQTO6GC6PV · pith_short_16: KVIQTO6GC6PVZVDX · pith_short_8: KVIQTO6G

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/KVIQTO6GC6PVZVDXZQMFBVGRPV \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 555109bbc6179f5cd477cc1850d4d17d75f7a1c411c8f577125b4c0c4a2143c6

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "9ffd0c4a9a11105978979c9f9d00e10ef2d389b310bcddf8d4736bce089a528b",
    "cross_cats_sorted": [
      "cs.DM"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "math.OC",
    "submitted_at": "2026-05-13T19:33:30Z",
    "title_canon_sha256": "a4ab96662b01f0ab7e03d12c26d5157a8c50013b407c91afd989cfc9322492ee"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.14058",
    "kind": "arxiv",
    "version": 1
  }
}