New Sketch Algorithm: Sparse Sign Embedding

[nathanielpritchard]

Here we implement a sparse sign embedding, which performs the sparse sign embedding from section 9.2. The value of this sketching routine is its ability to perform the sketch with a computational complexity that scales with the number of nonzeros in the sketching matrix.

Both Column and Row versions of this technique should be implemented that satisfy:

Row Sampler

1. Implementation

• Create a file in the directory linear_samplers.
• Create a mutable struct for the sampling method.
• Create a constructor with default values for your struct.
• Create a function sample (a template can be found in src/linear_samplers.jl):
  INPUTS:
  • 1. type, your mutable struct
  • 2. A, an AbstractMatrix
  • 3. b, an AbstractVector
  • 4. x, an AbstractVector
  • 5. iter an Int64
    OUTPUTS:
  • 1. S the sampling matrix
  • 2. SA the sampling matrix applied to A from the right.
  • 3. res the sketched residual SA * x - S * b
• Add an include("linear_samplers/[YOURFILE]") under the heading that best fits you method in src/linear_samplers.jl.
• Add import statements to src/RLinearAlgebra.jl with any functions from other packages that you use.
• Add your structure to the list of exported row samplers in src/RLinearAlgebra.jl.
• Add your structure to docs/src/api/linear_samplers.md under the appropiate heading.
• Add a procedural test to test/linear_samplers.

2. Pull request

• Give a specific title to pull request.
• Lay out the features added to the pull request.
• Tag two people to review your pull request.

Column Sampler

1. Implementation

• Create a file in the directory linear_samplers.

• Create a mutable struct for the sampling method.

• Create a constructor with default values for your struct.

• Create a function sample (a template can be found in src/linear_samplers.jl):
  INPUTS:

  • 1. type, your mutable struct
  • 2. A, an AbstractMatrix
  • 3. b, an AbstractVector
  • 4. x, an AbstractVector
  • 5. iter an Int64
    OUTPUTS:
  • 1. S the sampling matrix
  • 2. AS the sampling matrix applied to A from the right.
  • 3. res the full residual A * x - b (Note the difference from the row methods).
  • 4. grad the sketched residual SA'res.

• Add an include("linear_samplers/[YOURFILE]") under the heading that best fits you method in src/linear_samplers.jl.

• Add import statements to src/RLinearAlgebra.jl with any functions from other packages that you use.

• Add your structure to the list of exported row samplers in src/RLinearAlgebra.jl.

• Add your structure to docs/src/api/linear_samplers.md under the appropiate heading.

• Add a procedural test to test/linear_samplers.

2. Pull request

• Give a specific title to pull request.
• Lay out the features added to the pull request.
• Tag two people to review your pull request.