What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank

Pauli Miettinen; Rainer Gemulla; Stefan Neumann

RECORD

What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank

Stefan Neumann, Rainer Gemulla, Pauli Miettinen

Discrete Mathematics · Submitted 16 Sep 2016

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim We show that rounding rank is related to linear classification, dimensionality reduction, and nested matrices.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID1609.05034 (version 2)

Pith IDNWOCORB6, Pith's permanent record of this paper and its review

CitationPauli Miettinen, Rainer Gemulla, Stefan Neumann. "What You Will Gain By Rounding: Theory and Algorithms for Rounding Rank." arXiv:1609.05034 (2016). https://pith.science/paper/NWOCORB6

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 7,238 input tokens.

What the abstract itself states, as probabilities: claims first 0.05 · states limitation 0.08 · human participants 0.02 · controlled comparison 0.13 · randomized assignment 0.01 · states quantitative result 0.05 · compares with prior results 0.42 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

When factorizing binary matrices, we often have to make a choice between using expensive combinatorial methods that retain the discrete nature of the data and using continuous methods that can be more efficient but destroy the discrete structure. Alternatively, we can first compute a continuous factorization and subsequently apply a rounding procedure to obtain a discrete representation. But what will we gain by rounding? Will this yield lower reconstruction errors? Is it easy to find a low-rank matrix that rounds to a given binary matrix? Does it matter which threshold we use for rounding? Does it matter if we allow for only non-negative factorizations? In this paper, we approach these and further questions by presenting and studying the concept of rounding rank. We show that rounding rank is related to linear classification, dimensionality reduction, and nested matrices. We also report on an extensive experimental study that compares different algorithms for finding good factorizations under the rounding rank model.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	When factorizing binary matrices, we often have to make a choice between using expensive combinatorial methods that retain the discrete nature of the data and using continuous methods that can be more efficient but destroy the discrete structure.	background 1.00	0.06	0.02	asserted 0.92
s1	Alternatively, we can first compute a continuous factorization and subsequently apply a rounding procedure to obtain a discrete representation.	background 0.87	0.07	0.03	asserted 0.55
s2	But what will we gain by rounding?	gap 0.86	0.04	0.02	unclear 0.99
s3	Will this yield lower reconstruction errors?	gap 0.88	0.04	0.02	unclear 0.92
s4	Is it easy to find a low-rank matrix that rounds to a given binary matrix?	gap 0.91	0.05	0.02	unclear 0.84
s5	Does it matter which threshold we use for rounding?	gap 0.90	0.04	0.01	unclear 0.88
s6	Does it matter if we allow for only non-negative factorizations?	gap 0.81	0.05	0.02	unclear 0.88
s7	In this paper, we approach these and further questions by presenting and studying the concept of rounding rank.	contribution 0.98	0.89	0.08	asserted 0.88
s8	We show that rounding rank is related to linear classification, dimensionality reduction, and nested matrices.	result 0.58	0.91	0.24	asserted 1.00
s9	We also report on an extensive experimental study that compares different algorithms for finding good factorizations under the rounding rank model.	contribution 0.90	0.96	0.08	asserted 0.99

What kind of paper the classifier reports this is: method or tool 0.55 · evidence from observation or experiment 0.64.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

When factorizing binary matrices, we often have to make a choice between using expensive combinatorial methods that retain the discrete nature of the data and using continuous methods that can be more efficient but destroy the discrete structure. Alternatively, we can first compute a continuous factorization and subsequently apply a rounding procedure to obtain a discrete representation. But what will we gain by rounding? Will this yield lower reconstruction errors? Is it easy to find a low-rank matrix that rounds to a given binary matrix? Does it matter which threshold we use for rounding? Does it matter if we allow for only non-negative factorizations? In this paper, we approach these and further questions by presenting and studying the concept of rounding rank. We show that rounding rank is related to linear classification, dimensionality reduction, and nested matrices. We also report on an extensive experimental study that compares different algorithms for finding good factorizations under the rounding rank model.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

How Much Rank Does LoRA Need? Rank-Error Bounds for Transformer Attention
cs.LG 2026-08 conditional novelty 8.0 of 10

For a fixed target attention function, the best achievable rank-r LoRA attention error is bracketed by explicit functions of a task-weighted spectral tail T_r, including a saturation effect that can lower the needed rank.
Is Dimensionality a Barrier for Retrieval Models?
cs.LG 2026-05 unverdicted novelty 8.0 of 10

Dimension d = O(m^{-2} log n) nearly achieves the optimal margin m^rd(+∞, A) for retrieval embeddings, with matching lower bounds showing d = O(k log(n/k)) suffices and is necessary for m = Θ(k^{-1/2}) on k-sparse que...

How the literature uses it

1 arXiv paper cite this in 1 sentence

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it

Compares with it 1 paper

Sign rank and rounding rank concern finite, exact realization of prescribed sign or threshold patterns [ref] , whereas our closure rank allows a sequence of scores to diverge while its softmax converges.

How Much Rank Does LoRA Need? Rank-Error Bounds for Transformer Attention · Related work · 0.98

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.