3.1. Runtime of Hard Thresholding Pursuit on Large Sensing Matrices¶

# Configure JAX for 64-bit computing
from jax.config import config
config.update("jax_enable_x64", True)

import jax
import jax.numpy as jnp
import cr.sparse as crs
import cr.sparse.dict as crdict
import cr.sparse.data as crdata
import cr.sparse.pursuit.htp as htp
import cr.sparse.ef as ef

M = 2560;
N = 10240;
K = 200;

Phi = crdict.gaussian_mtx(crs.KEYS[0], M, N)

Phi.shape

(2560, 10240)

a = 1;
b = 2;
x0, omega = crdata.sparse_biuniform_representations(crs.KEYS[1], a, b, N, K)

y0 = Phi @ x0

y0.shape

(2560,)

u_bound = crdict.upper_frame_bound(Phi)
step_size = float(0.98 / u_bound)

sol = htp.matrix_solve_jit(Phi, y0, K, step_size=step_size)

print(sol.iterations)

perf = ef.RecoveryPerformance(Phi, y0, x0, sol=sol)

perf.print()

M: 2560, N: 10240, K: 200
x_norm: 21.520, y_norm: 21.477
x_hat_norm: 21.520, h_norm: 8.69e-14, r_norm: 9.13e-14
recovery_snr: 287.87 dB, measurement_snr: 287.43 dB
x_dr: 6.00 dB, y_dr: 73.26 dB, x_hat_dr: 5.999 dB
T0: [   10    64   270   293   330   341   450   467   506   515   555   577
 702   806   824   938   963   974   982  1129  1130  1199  1209
1242  1271  1445  1518  1528  1598  1673  1710  1772  1898  1922
2100  2109  2170  2196  2286  2415  2476  2531  2654  2674  2777
2875  2897  2931  2938  2979  3018  3070  3109  3117  3141  3206
3221  3405  3430  3447  3565  3612  3672  3673  3711  3788  3828
3930  3965  4004  4028  4060  4161  4241  4277  4323  4412  4427
4442  4517  4564  4655  4720  4735  4874  4899  4900  4956  5061
5156  5197  5207  5246  5468  5512  5571  5582  5634  5694  5711
5794  5927  5959  6015  6035  6141  6151  6212  6252  6257  6260
6385  6437  6543  6691  6742  6812  6854  6906  6915  6943  6959
7091  7140  7232  7241  7366  7534  7548  7603  7616  7634  7687
7760  7803  7942  8061  8103  8110  8119  8189  8201  8250  8265
8317  8427  8452  8646  8705  8736  8765  8857  8870  8879  8935
8968  9033  9084  9232  9251  9296  9360  9396  9437  9462  9515
9526  9563  9573  9578  9643  9652  9678  9734  9744  9784  9804
9896  9914  9953  9954 10056 10088 10191]
R0: [   10    64   270   293   330   341   450   467   506   515   555   577
 702   806   824   938   963   974   982  1129  1130  1199  1209
1242  1271  1445  1518  1528  1598  1673  1710  1772  1898  1922
2100  2109  2170  2196  2286  2415  2476  2531  2654  2674  2777
2875  2897  2931  2938  2979  3018  3070  3109  3117  3141  3206
3221  3405  3430  3447  3565  3612  3672  3673  3711  3788  3828
3930  3965  4004  4028  4060  4161  4241  4277  4323  4412  4427
4442  4517  4564  4655  4720  4735  4874  4899  4900  4956  5061
5156  5197  5207  5246  5468  5512  5571  5582  5634  5694  5711
5794  5927  5959  6015  6035  6141  6151  6212  6252  6257  6260
6385  6437  6543  6691  6742  6812  6854  6906  6915  6943  6959
7091  7140  7232  7241  7366  7534  7548  7603  7616  7634  7687
7760  7803  7942  8061  8103  8110  8119  8189  8201  8250  8265
8317  8427  8452  8646  8705  8736  8765  8857  8870  8879  8935
8968  9033  9084  9232  9251  9296  9360  9396  9437  9462  9515
9526  9563  9573  9578  9643  9652  9678  9734  9744  9784  9804
9896  9914  9953  9954 10056 10088 10191]
Overlap: [   10    64   270   293   330   341   450   467   506   515   555   577
 702   806   824   938   963   974   982  1129  1130  1199  1209
1242  1271  1445  1518  1528  1598  1673  1710  1772  1898  1922
2100  2109  2170  2196  2286  2415  2476  2531  2654  2674  2777
2875  2897  2931  2938  2979  3018  3070  3109  3117  3141  3206
3221  3405  3430  3447  3565  3612  3672  3673  3711  3788  3828
3930  3965  4004  4028  4060  4161  4241  4277  4323  4412  4427
4442  4517  4564  4655  4720  4735  4874  4899  4900  4956  5061
5156  5197  5207  5246  5468  5512  5571  5582  5634  5694  5711
5794  5927  5959  6015  6035  6141  6151  6212  6252  6257  6260
6385  6437  6543  6691  6742  6812  6854  6906  6915  6943  6959
7091  7140  7232  7241  7366  7534  7548  7603  7616  7634  7687
7760  7803  7942  8061  8103  8110  8119  8189  8201  8250  8265
8317  8427  8452  8646  8705  8736  8765  8857  8870  8879  8935
8968  9033  9084  9232  9251  9296  9360  9396  9437  9462  9515
9526  9563  9573  9578  9643  9652  9678  9734  9744  9784  9804
9896  9914  9953  9954 10056 10088 10191]
Correct atoms: 200. Ratio: 1.00, perfect_support_recovery: True
success: True

%timeit htp.matrix_solve_jit(Phi, y0, K, step_size=step_size).I.block_until_ready()

114 ms ± 30.4 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

CR-Sparse Companion

3.1. Runtime of Hard Thresholding Pursuit on Large Sensing Matrices¶