dizcza / sparse-representation Goto Github PK

View Code? Open in Web Editor NEW

10.0 2.0 2.0 414 KB

Sparse representation solvers for P0- and P1-problems

Home Page: https://sparse-representation.readthedocs.io

License: MIT License

Python 97.72% MATLAB 2.28%

sparse-representations sparse-coding matching-pursuit basis-pursuit pytorch python neural-networks

sparse-representation's Introduction

Sparse Representation Algorithms

Python solvers for P0- and P1-problems.

P0-epsilon problem: min_z ||z||_0 s.t. ||Az - x|| < eps
P1-epsilon problem: min_z ||z||_1 s.t. ||Az - x|| < eps
Q1-epsilon problem: min_z ||Az - x||^2 + λ||z||_1

where z is a sparse representation of the input x, and A is a dictionary matrix (either fixed or learned).

Documentation is available at https://sparse-representation.readthedocs.io

The theoretical foundations of the implemented functional are in edX course Sparse Representations in Signal and Image Processing.

Algorithms

Coherence of a matrix

Mutual Coherence
Babbel Function
Spark of a matrix

Solving P0- and P1-epsilon problems with a fixed dictionary

Greedy algorithms, approximating the P0-problem:
- Orthogonal Matching Pursuit (OMP)
- Least Squares OMP (LS-OMP)
- Matching Pursuit (MP)
- Weak Matching Pursuit (WMP)
- Thresholding Algorithm (THR)
Relaxation algorithms, approximating the P0-problem:
- Basis Pursuit (L1-relaxation)
- Basis Pursuit + ADMM
- Iterative Shrinkage Algorithm (ISTA, Fast ISTA)

Dictionary learning

BasisPursuit dictionary learning (similar to MOD)
Learned Iterative Shrinkage-Thresholding Algorithm (LISTA)

sparse.nn module contains PyTorch implementation of the listed above algorithms.

Quick start example

Fixed dictionary

Reproduce with edX/finproj/project2_all.py

To illustrate an example with a fixed dictionary, we

simulate an image x of size n x n, constructed with bars;
add noise and corrupt the image -> x_noisy;
generate a fixed dictionary matrix A of size n^2 x m (m >> n^2) with random bars as atoms (columns);
reconstruct x' from x_noisy by seeking the sparsest vector z such that Az ≈ x.

Learned dictionary

Start a Visdom server and run the examples with

$ python -m visdom.server
$ python sparse/examples/basis_pursuit_pytorch.py

Then navigate to localhost:8097 to see the training progress.

The "output sparsity" is the sparsity of the embedding vector from which the original image is reconstructed.

Demo

More examples are on http://85.217.171.57:8097. Choose environments with MatchingPursuit.

Installation

$ git clone https://github.com/dizcza/sparse-representation.git
$ cd sparse-representation
$ pip install -e .[extra]

Extra requirements install PyTorch for sparse.nn module.

sparse-representation's People

Contributors

Stargazers

Watchers

Forkers

xgxg1314 vishalbelsare

sparse-representation's Issues

RuntimeError: indices should be either on cpu or on the same device as the indexed tensor (cpu)

When i tried the demo python sparse/examples/basis_pursuit_pytorch.py, the error occurred

> python sparse/examples/basis_pursuit_pytorch.py                                                         
Checkpoint '/home/j/.cache/mighty/checkpoints/2023.11.27 MatchingPursuit: MNIST TrainMatchingPursuit Lo
ssPenalty(MSELoss).pt' doesn't exist. Nothing to restore.                                                 
MatchingPursuit(                                                                                          
  in_features=784, out_features=256                                                                       
  (solver): BasisPursuitADMM(lambd=0.1, tol=0.0001, max_iters=100)                                        
)                                                                                                         
Setting up a new session...                                                                               
Monitor is opened at http://localhost:8097. Choose environment '2023.11.27 MatchingPursuit: MNIST TrainMat
chingPursuit LossPenalty(MSELoss)'. 
Traceback (most recent call last):                                                                        
  File "/home/june/projects/sparse/sparse-representation/sparse/examples/basis_pursuit_pytorch.py", line 1
14, in <module>                                                                                           
    train_lista()                                                                                         
  File "/home/june/projects/sparse/sparse-representation/sparse/examples/basis_pursuit_pytorch.py", line 9
1, in train_lista                                                                                         
    model_ref = train_matching_pursuit(dataset_cls=dataset_cls)                                           
  File "/home/june/projects/sparse/sparse-representation/sparse/examples/basis_pursuit_pytorch.py", line 8
6, in train_matching_pursuit                                                                              
    trainer.train(n_epochs=n_epochs, mutual_info_layers=0)                                                
  File "/home/june/anaconda3/envs/sparse/lib/python3.9/site-packages/mighty/trainer/trainer.py", line 624,
 in train                                                                                                 
    self.train_epoch(epoch=epoch)                                                                         
  File "/home/june/anaconda3/envs/sparse/lib/python3.9/site-packages/mighty/trainer/trainer.py", line 520,
 in train_epoch                                                                                           
    loss = self.train_batch(batch)
  File "/home/june/anaconda3/envs/sparse/lib/python3.9/site-packages/mighty/trainer/gradient.py", line 73, in train_batch
    outputs = self._forward(batch)
  File "/home/june/anaconda3/envs/sparse/lib/python3.9/site-packages/mighty/trainer/trainer.py", line 360, in _forward
    return self.model(input)
  File "/home/june/anaconda3/envs/sparse/lib/python3.9/site-packages/torch/nn/modules/module.py", line 1190, in _call_impl
    return forward_call(*input, **kwargs)
  File "/home/june/projects/sparse/sparse-representation/sparse/nn/model.py", line 97, in forward
    z = solver.solve(A=self.weight.t(), b=x)
  File "/home/june/projects/sparse/sparse-representation/sparse/nn/solver.py", line 134, in solve
    v_solution, dv_norm, iteration = basis_pursuit_admm(
  File "/home/june/projects/sparse/sparse-representation/sparse/nn/solver.py", line 105, in basis_pursuit_admm
    v, u, A_dot_b = _reduce(solved, solved_batch, v_solution, v, u,
  File "/home/june/projects/sparse/sparse-representation/sparse/nn/solver.py", line 34, in _reduce
    became_solved_ids = unsolved_ids[keys]
RuntimeError: indices should be either on cpu or on the same device as the indexed tensor (cpu)

There are 2 gpus in Ubuntu system.
but i modify use_cuda = False, the error occurred again.
There may be some device control mistake.