Spark under 2-D fourier sampling. Biswas, S., Dasgupta, S., Jacob, M., & Mudumbai, R. In 2015 23rd European Signal Processing Conference (EUSIPCO), pages 2821-2824, Aug, 2015.
Paper doi abstract bibtex We consider the spark of submatrices of 2D-DFT matrices obtained by removing certain rows and relate it to the spark of associated 1D-DFT submatrices. A matrix has spark m if its smallest number of linearly dependent columns equals m. To recover an arbitrary fc-sparse vector, the spark of an observation matrix must exceed 2fc. We consider how to choose the rows of the 2D-DFT matrix so that it is full spark, i.e. its spark equals one more than its row dimension. We consider submatrices resulting from two sets of sampling patterns in frequency space: On a straight line and on a rectangular grid. We show that in the latter case full spark is rarely obtainable, though vectors with certain sparsity patterns can still be recovered. In the former case we provide a necessary and sufficient condition for full spark, and show that lines with integer slopes cannot attain it.
@InProceedings{7362899,
author = {S. Biswas and S. Dasgupta and M. Jacob and R. Mudumbai},
booktitle = {2015 23rd European Signal Processing Conference (EUSIPCO)},
title = {Spark under 2-D fourier sampling},
year = {2015},
pages = {2821-2824},
abstract = {We consider the spark of submatrices of 2D-DFT matrices obtained by removing certain rows and relate it to the spark of associated 1D-DFT submatrices. A matrix has spark m if its smallest number of linearly dependent columns equals m. To recover an arbitrary fc-sparse vector, the spark of an observation matrix must exceed 2fc. We consider how to choose the rows of the 2D-DFT matrix so that it is full spark, i.e. its spark equals one more than its row dimension. We consider submatrices resulting from two sets of sampling patterns in frequency space: On a straight line and on a rectangular grid. We show that in the latter case full spark is rarely obtainable, though vectors with certain sparsity patterns can still be recovered. In the former case we provide a necessary and sufficient condition for full spark, and show that lines with integer slopes cannot attain it.},
keywords = {compressed sensing;discrete Fourier transforms;sampling methods;2D Fourier sampling;2D-DFT matrices;1D-DFT submatrices;arbitrary fc-sparse vector;observation matrix;frequency space;full spark;compressed sensing;Sparks;Discrete Fourier transforms;Magnetic resonance imaging;Sparse matrices;Europe;Signal processing;Jacobian matrices;Coprime sensing;full spark;compressed sensing;two dimensional;Fourier Sampling},
doi = {10.1109/EUSIPCO.2015.7362899},
issn = {2076-1465},
month = {Aug},
url = {https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570103923.pdf},
}
Downloads: 0
{"_id":"L7ecLXCLHFtFwRHrX","bibbaseid":"biswas-dasgupta-jacob-mudumbai-sparkunder2dfouriersampling-2015","authorIDs":[],"author_short":["Biswas, S.","Dasgupta, S.","Jacob, M.","Mudumbai, R."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["S."],"propositions":[],"lastnames":["Biswas"],"suffixes":[]},{"firstnames":["S."],"propositions":[],"lastnames":["Dasgupta"],"suffixes":[]},{"firstnames":["M."],"propositions":[],"lastnames":["Jacob"],"suffixes":[]},{"firstnames":["R."],"propositions":[],"lastnames":["Mudumbai"],"suffixes":[]}],"booktitle":"2015 23rd European Signal Processing Conference (EUSIPCO)","title":"Spark under 2-D fourier sampling","year":"2015","pages":"2821-2824","abstract":"We consider the spark of submatrices of 2D-DFT matrices obtained by removing certain rows and relate it to the spark of associated 1D-DFT submatrices. A matrix has spark m if its smallest number of linearly dependent columns equals m. To recover an arbitrary fc-sparse vector, the spark of an observation matrix must exceed 2fc. We consider how to choose the rows of the 2D-DFT matrix so that it is full spark, i.e. its spark equals one more than its row dimension. We consider submatrices resulting from two sets of sampling patterns in frequency space: On a straight line and on a rectangular grid. We show that in the latter case full spark is rarely obtainable, though vectors with certain sparsity patterns can still be recovered. In the former case we provide a necessary and sufficient condition for full spark, and show that lines with integer slopes cannot attain it.","keywords":"compressed sensing;discrete Fourier transforms;sampling methods;2D Fourier sampling;2D-DFT matrices;1D-DFT submatrices;arbitrary fc-sparse vector;observation matrix;frequency space;full spark;compressed sensing;Sparks;Discrete Fourier transforms;Magnetic resonance imaging;Sparse matrices;Europe;Signal processing;Jacobian matrices;Coprime sensing;full spark;compressed sensing;two dimensional;Fourier Sampling","doi":"10.1109/EUSIPCO.2015.7362899","issn":"2076-1465","month":"Aug","url":"https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570103923.pdf","bibtex":"@InProceedings{7362899,\n author = {S. Biswas and S. Dasgupta and M. Jacob and R. Mudumbai},\n booktitle = {2015 23rd European Signal Processing Conference (EUSIPCO)},\n title = {Spark under 2-D fourier sampling},\n year = {2015},\n pages = {2821-2824},\n abstract = {We consider the spark of submatrices of 2D-DFT matrices obtained by removing certain rows and relate it to the spark of associated 1D-DFT submatrices. A matrix has spark m if its smallest number of linearly dependent columns equals m. To recover an arbitrary fc-sparse vector, the spark of an observation matrix must exceed 2fc. We consider how to choose the rows of the 2D-DFT matrix so that it is full spark, i.e. its spark equals one more than its row dimension. We consider submatrices resulting from two sets of sampling patterns in frequency space: On a straight line and on a rectangular grid. We show that in the latter case full spark is rarely obtainable, though vectors with certain sparsity patterns can still be recovered. In the former case we provide a necessary and sufficient condition for full spark, and show that lines with integer slopes cannot attain it.},\n keywords = {compressed sensing;discrete Fourier transforms;sampling methods;2D Fourier sampling;2D-DFT matrices;1D-DFT submatrices;arbitrary fc-sparse vector;observation matrix;frequency space;full spark;compressed sensing;Sparks;Discrete Fourier transforms;Magnetic resonance imaging;Sparse matrices;Europe;Signal processing;Jacobian matrices;Coprime sensing;full spark;compressed sensing;two dimensional;Fourier Sampling},\n doi = {10.1109/EUSIPCO.2015.7362899},\n issn = {2076-1465},\n month = {Aug},\n url = {https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570103923.pdf},\n}\n\n","author_short":["Biswas, S.","Dasgupta, S.","Jacob, M.","Mudumbai, R."],"key":"7362899","id":"7362899","bibbaseid":"biswas-dasgupta-jacob-mudumbai-sparkunder2dfouriersampling-2015","role":"author","urls":{"Paper":"https://www.eurasip.org/proceedings/eusipco/eusipco2015/papers/1570103923.pdf"},"keyword":["compressed sensing;discrete Fourier transforms;sampling methods;2D Fourier sampling;2D-DFT matrices;1D-DFT submatrices;arbitrary fc-sparse vector;observation matrix;frequency space;full spark;compressed sensing;Sparks;Discrete Fourier transforms;Magnetic resonance imaging;Sparse matrices;Europe;Signal processing;Jacobian matrices;Coprime sensing;full spark;compressed sensing;two dimensional;Fourier Sampling"],"metadata":{"authorlinks":{}},"downloads":0},"bibtype":"inproceedings","biburl":"https://raw.githubusercontent.com/Roznn/EUSIPCO/main/eusipco2015url.bib","creationDate":"2021-02-13T17:31:52.645Z","downloads":0,"keywords":["compressed sensing;discrete fourier transforms;sampling methods;2d fourier sampling;2d-dft matrices;1d-dft submatrices;arbitrary fc-sparse vector;observation matrix;frequency space;full spark;compressed sensing;sparks;discrete fourier transforms;magnetic resonance imaging;sparse matrices;europe;signal processing;jacobian matrices;coprime sensing;full spark;compressed sensing;two dimensional;fourier sampling"],"search_terms":["spark","under","fourier","sampling","biswas","dasgupta","jacob","mudumbai"],"title":"Spark under 2-D fourier sampling","year":2015,"dataSources":["eov4vbT6mnAiTpKji","knrZsDjSNHWtA9WNT"]}