patternMinor
Need clarification about the use of Big-O to describe matrix sparsity
Viewed 0 times
sparsityclarificationtheneedbigdescribeaboutusematrix
Problem
In one of my courses, Big-O notation was used for defining what a sparse matrix is, under the context of qualifying for suitability for a particular set of linear algebra algorithms. I looked around on the net, and only found more such uses that I have an issue with.
To say a matrix is sparse if it has O(n) non-zero elements, for example, is illogical. The sentence doesn't even parse right? When we talk about Big-O, we are talking about functions. So it would make sense to say for example, as a way to describe a property of a set of matrices, maybe produced by a function that builds or bounds particular types of matrices, parameterized by the dimensions. In this case however, it really would not say anything about a particular matrix in the set in terms of sparsity. For example, in such a O(n) set, every matrix of size less than 1 trillion^2 could have no non-zero elements.
I have the same logical problem with qualifications for graphs sparsity.
But I cannot seam to find any precise explanation for why Big-O is used in such ways, or whether it is used the correct way or is an abuse of notation.
To say a matrix is sparse if it has O(n) non-zero elements, for example, is illogical. The sentence doesn't even parse right? When we talk about Big-O, we are talking about functions. So it would make sense to say for example, as a way to describe a property of a set of matrices, maybe produced by a function that builds or bounds particular types of matrices, parameterized by the dimensions. In this case however, it really would not say anything about a particular matrix in the set in terms of sparsity. For example, in such a O(n) set, every matrix of size less than 1 trillion^2 could have no non-zero elements.
I have the same logical problem with qualifications for graphs sparsity.
But I cannot seam to find any precise explanation for why Big-O is used in such ways, or whether it is used the correct way or is an abuse of notation.
Solution
What you have encountered is a very common convention. The sparsity assumption is probably in some algorithmic context: given a sparse matrix, here is an efficient algorithm that solves some problem. For example:
Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$.
What this really means is:
For every $C > 0$ there is an algorithm that, given a matrix with at most $Cn$ non-zero elements, does X in $O(n^2)$.
The constant hidden inside the big O depends on $C$.
A similar convention explains the following sentence:
There is a function $f\colon \{0,1\}^n \to \{0,1\}$ whose maximal influence is $O(\log n/n)$.
(The meaning of maximal influence is not important here.) What this really means is:
There is a sequence of functions $f_1,f_2,\ldots$ such that $f_n\colon \{0,1\}^n \to \{0,1\}$ and the maximal influence of $f_n$ is $O(\log n/n)$.
Once you get used to this convention, all these seemingly meaningless sentences will acquire their full meaning.
Given a matrix with $O(n)$ non-zero elements, there is an algorithm to do X in $O(n^2)$.
What this really means is:
For every $C > 0$ there is an algorithm that, given a matrix with at most $Cn$ non-zero elements, does X in $O(n^2)$.
The constant hidden inside the big O depends on $C$.
A similar convention explains the following sentence:
There is a function $f\colon \{0,1\}^n \to \{0,1\}$ whose maximal influence is $O(\log n/n)$.
(The meaning of maximal influence is not important here.) What this really means is:
There is a sequence of functions $f_1,f_2,\ldots$ such that $f_n\colon \{0,1\}^n \to \{0,1\}$ and the maximal influence of $f_n$ is $O(\log n/n)$.
Once you get used to this convention, all these seemingly meaningless sentences will acquire their full meaning.
Context
StackExchange Computer Science Q#76663, answer score: 2
Revisions (0)
No revisions yet.