Matrix sketching using analog crossbar architectures

Patent metadata

Field	Value
Publication number	US-11520855-B2
Application number	US-202016874819-A
Country	US
Kind code	B2
Filing date	May 15, 2020
Priority date	May 15, 2020
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

A computer-implemented method is presented for performing matrix sketching by employing an analog crossbar architecture. The method includes low rank updating a first matrix for a first period of time, copying the first matrix into a dynamic correction computing device, switching to a second matrix to low rank update the second matrix for a second period of time, as the second matrix is low rank updated, feeding the first matrix with first stochastic pulses to reset the first matrix back to a first matrix symmetry point, copying the second matrix into the dynamic correction computing device, switching back to the first matrix to low rank update the first matrix for a third period of time, and as the first matrix is low rank updated, feeding the second matrix with second stochastic pulses to reset the second matrix back to a second matrix symmetry point.

First claim

The invention claimed is:

1. A computer-implemented method executed on a processor for performing matrix sketching, the method comprising:
placing a first matrix and a second matrix in an analog crossbar architecture;
low rank updating the first matrix for a first period of time;
copying the first matrix into a dynamic correction computing device;
switching to the second matrix to low rank update the second matrix for a second period of time;
as the second matrix is low rank updated, feeding the first matrix with first stochastic pulses to reset the first matrix back to a first matrix symmetry point;
copying the second matrix into the dynamic correction computing device;
switching back to the first matrix to low rank update the first matrix for a third period of time; and
as the first matrix is low rank updated, feeding the second matrix with second stochastic pulses to reset the second matrix back to a second matrix symmetry point.

2. The method of claim 1 , wherein the first and second matrices include streaming data.

3. The method of claim 2 , wherein the streaming data is normalized to prevent asymmetry effects.

4. The method of claim 3 , wherein the low rank updating of the first and second matrices is scaled to adjust a final sketching matrix to between (−0.1, 0.1) for a full range of (−1, 1) to operate near the first and second matrix asymmetry points.

5. The method of claim 4 , wherein once the matrix sketching is applied to an entire input, a final sketching matrix is moved to a digital computer to perform a regression analysis.

6. The method of claim 1 , wherein the dynamic correction computing device concurrently corrects the first and second matrices.

7. A non-transitory computer-readable storage medium comprising a computer-readable program executed on a processor in a data processing system for performing matrix sketching, wherein the computer-readable program when executed on the processor causes a computer to perform the steps of:
placing a first matrix and a second matrix in an analog crossbar architecture;
low rank updating the first matrix for a first period of time;
copying the first matrix into a dynamic correction computing device;
switching to the second matrix to low rank update the second matrix for a second period of time;
as the second matrix is low rank updated, feeding the first matrix with first stochastic pulses to reset the first matrix back to a first matrix symmetry point;
copying the second matrix into the dynamic correction computing device;
switching back to the first matrix to low rank update the first matrix for a third period of time; and
as the first matrix is low rank updated, feeding the second matrix with second stochastic pulses to reset the second matrix back to a second matrix symmetry point.

8. The non-transitory computer-readable storage medium of claim 7 , wherein the first and second matrices include streaming data.

9. The non-transitory computer-readable storage medium of claim 8 , wherein the streaming data is normalized to prevent asymmetry effects.

10. The non-transitory computer-readable storage medium of claim 9 , wherein the low rank updating of the first and second matrices is scaled to adjust a final sketching matrix to between (−0.1, 0.1) for a full range of (−1, 1) to operate near the first and second matrix asymmetry points.

11. The non-transitory computer-readable storage medium of claim 10 , wherein once the matrix sketching is applied to an entire input, a final sketching matrix is moved to a digital computer to perform a regression analysis.

12. The non-transitory computer-readable storage medium of claim 7 , wherein the dynamic correction computing device concurrently corrects the first and second matrices.

13. A system for performing matrix sketching, the system comprising:
a memory; and
one or more processors in communication with the memory configured to:
place a first matrix and a second matrix in an analog crossbar architecture;
low rank update the first matrix for a first period of time;
copy the first matrix into a dynamic correction computing device;
switch to the second matrix to low rank update the second matrix for a second period of time;
as the second matrix is low rank updated, feed the first matrix with first stochastic pulses to reset the first matrix back to a first matrix symmetry point;
copy the second matrix into the dynamic correction computing device;
switch back to the first matrix to low rank update the first matrix for a third period of time; and
as the first matrix is low rank updated, feed the second matrix with second stochastic pulses to reset the second matrix back to a second matrix symmetry point.

14. The system of claim 13 , wherein the first and second matrices include streaming data.

15. The system of claim 14 , wherein the streaming data is normalized to prevent asymmetry effects.

16. The system of claim 15 , wherein the low rank updating of the first and second matrices is scaled to adjust a final sketching matrix to between (−0.1, 0.1) for a full range of (−1, 1) to operate near the first and second matrix asymmetry points.

17. The system of claim 16 , wherein once the matrix sketching is applied to an entire input, the final sketching matrix is moved to a digital computer to perform a regression analysis.

18. The system of claim 13 , wherein the dynamic correction computing device concurrently corrects the first and second matrices.

19. A computer-implemented method executed on a processor for performing matrix sketching, the method comprising:
applying dimensionality reduction to streaming data using outer product low rank updates;
once the dimensionality reduction is applied to an entire input, moving a sketched matrix to a digital computer to perform regression analysis, wherein the sketched matrix is derived from a first matrix and a second matrix used in parallel in a toggling manner, the first and second matrices placed in an analog crossbar architecture;
low rank updating the first matrix for a first period of time;
copying the first matrix into a dynamic correction computing device; and
switching to the second matrix to low rank update the second matrix for a second period of time.

20. The method of claim 19 , further comprising:
as the second matrix is low rank updated, feeding the first matrix with first stochastic pulses to reset the first matrix back to a first matrix symmetry point;
copying the second matrix into the dynamic correction computing device;
switching back to the first matrix to tow rank update the first matrix for a third period of time; and
as the first matrix is low rank updated, feeding the second matrix with second stochastic pulses to reset the second matrix back to a second matrix symmetry point.

21. A system for performing matrix sketching, the system comprising:
a memory; and
one or more processors in communication with the memory configured to:
apply dimensionality reduction to streaming data using outer product low rank updates;
once the dimensionality reduction is applied to an entire input, move a sketched matrix to a digital computer to perform regression analysis, wherein the sketched matrix is derived from a first matrix and a second matrix used in parallel in a toggling manner, the first and second matrices placed in an analog crossbar architecture;
low rank update the first matrix for a first period of time;
copy the first matrix into a dynamic correction computing device; and
switch to the se

Assignees

• IBM
• Univ Ramot
• Int Business Machines Corportation

Inventors

• Horesh Lior
• Onen Oguzhan Murat
• Avron Haim
• Gokmen Tayfun
• Kalantzis Vasileios
• Ubaru Shashanka

Classifications

• G06N3/065 Primary

  Analogue means · CPC title

• G06F2119/12

  Timing analysis or timing optimisation · CPC title

• G06F30/392 Primary

  Floor-planning or layout, e.g. partitioning or placement · CPC title

• G06F30/27

  using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model · CPC title

• G06F30/373 Primary

  Design optimisation · CPC title