{"id":1668,"date":"2023-11-27T17:09:04","date_gmt":"2023-11-27T17:09:04","guid":{"rendered":"https:\/\/www.ethanepperly.com\/?p=1668"},"modified":"2024-02-13T20:09:44","modified_gmt":"2024-02-13T20:09:44","slug":"which-sketch-should-i-use","status":"publish","type":"post","link":"https:\/\/www.ethanepperly.com\/index.php\/2023\/11\/27\/which-sketch-should-i-use\/","title":{"rendered":"Which Sketch Should I Use?"},"content":{"rendered":"\n

This is the second of a sequence of two posts on sketching, which I’m doing on the occasion of my new paper<\/a> on the numerical stability<\/a> of the iterative sketching method<\/a>. For more on what sketching is and how it can be used to solve computational problems, I encourage you to check out the first post<\/a>.<\/p>\n\n\n\n

The goals of this post are more narrow. I seek to answer the question:<\/p>\n\n\n\n

\n

Which sketching matrix should I use?<\/p>\n<\/blockquote>\n\n\n\n

To cut to the chase, my answer to this question is:<\/p>\n\n\n\n

\n

Sparse sign embeddings<\/a> are a sensible default for sketching.<\/p>\n<\/blockquote>\n\n\n\n

There are certainly cases when sparse sign embeddings are not the best type of sketch to use, but I hope to convince you that they’re a good sketching matrix to use for most purposes.<\/p>\n\n\n\n

Experiments<\/h2>\n\n\n\n

Let’s start things off with some numerical experiments.1<\/a><\/sup>Code for all numerical experiments can be found on the blogpost<\/em> branch of the Github<\/a> for my recent paper<\/a>.<\/span> We’ll compare three types of sketching matrices: Gaussian embeddings<\/a>, a subsampled randomized trigonometric transform<\/a> (SRTT), and sparse sign embeddings<\/a>. See the last post<\/a> for descriptions of these sketching matrices. I’ll discuss a few additional types of sketching matrices that require more discussion at the end of this post.<\/p>\n\n\n\n

Recall that a sketching matrix \"S \in \real^{d\times n}\" seeks to compress a high-dimensional matrix \"A \in \real^{n\times k}\" or vector \"b\in\real^n\" to a lower-dimensional sketched matrix \"SA\" or vector \"Sb\". The quality of a sketching matrix for a matrix \"A\" is measured by its distortion \"\varepsilon\", defined to be the smallest number \"\varepsilon > 0\" such that

  <\/span>   <\/span>\"\[(1-\varepsilon) \norm{x} \le \norm{Sx} \le (1+\varepsilon) \norm{x} \quad \text{for every } x \in \operatorname{col}(A).\]\"<\/p>Here, \"\operatorname{col}(A)\" denotes the column space<\/a> of the matrix \"A\".<\/p>\n\n\n\n

Timing<\/h3>\n\n\n\n

We begin with timing test. We will measure three different times for each embedding:<\/p>\n\n\n\n

    \n
  1. Construction.<\/strong> The time required to generate the sketching matrix \"S\".<\/li>\n\n\n\n
  2. Vector apply.<\/strong> The time to apply the sketch to a single vector.<\/li>\n\n\n\n
  3. Matrix apply.<\/strong> The time to apply the sketch to an \"n\times 200\" matrix.<\/li>\n<\/ol>\n\n\n\n

    We will test with input dimension \"n = 10^6\" (one million) and output dimension \"d = 400\". For the SRTT, we use the discrete cosine transform<\/a> as our trigonometric transform. For the sparse sign embedding, we use a sparsity parameter \"\zeta = 8\".<\/p>\n\n\n\n

    Here are the results (timings averaged over 20 trials):<\/p>\n\n\n

    \n
    \"\"<\/figure><\/div>\n\n\n

    Our conclusions are as follows:<\/p>\n\n\n\n