title: R: Find optimal sub-matrix
body: <p>I have a large symmetric matrix and want to reduce it to the much smaller matrix matrix_small with rows(matrix_small) = n. The mean of matrix_small should be maximized. <strong>Is there are way to achieve this goal in R with a better algorithm than I already have?</strong> Better is either faster with the same mean or a higher mean with the same speed.</p>
  
  <p>I feel like there should be a smarter way than to search the min so often. But I'm not aware of a way to set an SQL-like index for a Matrix in R to increase performance.</p>
  
  <pre><code>library(microbenchmark)
  set.seed(2016)
  sym_matrix &lt;- matrix(runif(1e+06), ncol = 1000)
  sym_matrix[lower.tri(sym_matrix)] &lt;- t(sym_matrix)[lower.tri(sym_matrix)]
  diag(sym_matrix) &lt;- NA
  
  rownames(sym_matrix) &lt;- 1:1000
  colnames(sym_matrix) &lt;- 1:1000
  
  findNrows &lt;- function(sym_matrix, nrows){
  # Return a matrix with rows(matrix) = nrows.
  # mean(matrix) should be maximized 
    set.seed(2017)
    k &lt;- nrow(sym_matrix)
    for (i in nrows:(k-1)) { #eliminate rows with minimum values
      min_rows &lt;- arrayInd(which.min(sym_matrix), dim(sym_matrix))
      choose_row &lt;- sample(min_rows, 1)
      sym_matrix &lt;- sym_matrix[-choose_row, -choose_row]
    }
    sym_matrix
  }
  
  microbenchmark(findNrows(sym_matrix = sym_matrix, nrows = 10), times = 25L) 
  mean(findNrows(sym_matrix = sym_matrix, nrows = 10), na.rm = TRUE)
  </code></pre>