MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

I'd like to sample the elements of a symmetric square matrix uniformly. For example, for a $N\times N$ matrix, I'd like to only keep $\alpha$% of the matrix elements to build a sparse matrix, while keeping the symmetry property.

A simple method would be to scan the upper right part of the matrix, generating a random number uniformly between 0 and 1 and compare to $\alpha/2$ to accept or reject the element, and symmetrize the matrix at the end.

However, in my case, sampling a row is costly while sampling a column is not : I'd like to minimize the number of rows that I will visit. For example, in the strategy above, every row is visited while the last row will have only have a single element visited checked: this is thus not optimal since I'll need to access the last row (which is very costly) to decide for a single element. I'd rather discard as many rows as possible if the symmetry property ensures that they will be covered anyway.

Hence, a solution could be to randomly choose $\sqrt{\alpha} N$ rows and sample each element of this row with a probability $\sqrt\alpha$, and symmetrize afterwards. However, I am not sure this would produce a uniform random sampling, similar to the one I would obtain with the first strategy.

What would be the best strategy while maintaining the uniform sampling property ?

Please, don't hesitate to tell me whether the question is not clear enough, or should be rather asked on StackOverflow. Thanks!

2 better explanation ?; added 115 characters in body; deleted 4 characters in body

I'd like to sample the elements of a symmetric matrix uniformly. For example, for a $N\times N$ matrix, I'd like to only keep $\alpha$% of the matrix elements to build a sparse matrix, while keeping the symmetry property.

A simple method would be to scan the upper right part of the matrix, generating a random number uniformly between 0 and 1 and compare to $\alpha/2$ to accept or reject the element, and symmetrize the matrix at the end.

However, in my case, sampling a row is costly while sampling a column is not : I'd like to minimize the number of rows that I will visit. For example, if I decide that the element $(i,j)$ should be in my final sparse matrix, but that for no other $k\neq j$, the elements $(i,k)$ are presentstrategy above, then I'd rather put the last row will have only a single element $(j,i)$ visited : this is thus not optimal since it will avoid sampling I'll need to access the last row $i$ (which is very costly) to decide for a single element$j$, while . I'd rather discard as many rows as possible if the row $j$ may symmetry property ensures that they will be sampled more denselycovered anyway.

What would be the best strategy while maintaining the uniform sampling property ?

Please, don't hesitate to tell me whether the question is not clear enough, or should be rather asked on StackOverflow. Thanks!

1

# Random sampling a symmetric matrix

I'd like to sample the elements of a symmetric matrix uniformly. For example, for a $N\times N$ matrix, I'd like to only keep $\alpha$% of the matrix elements to build a sparse matrix, while keeping the symmetry property.

A simple method would be to scan the upper right part of the matrix, generating a random number uniformly between 0 and 1 and compare to $\alpha/2$ to accept or reject the element, and symmetrize the matrix at the end.

However, in my case, sampling a row is costly while sampling a column is not : I'd like to minimize the number of rows that I will visit. For example, if I decide that the element $(i,j)$ should be in my final sparse matrix, but that for no other $k\neq j$, the elements $(i,k)$ are present, then I'd rather put the element $(j,i)$ since it will avoid sampling the row $i$ for a single element $j$, while the row $j$ may be sampled more densely.

What would be the best strategy while maintaining the uniform sampling property ?

Please, don't hesitate to tell me whether the question is not clear enough, or should be rather asked on StackOverflow. Thanks!