Skip to main content
SpringerLink
Log in

Sparse Coding with Anomaly Detection

  • Published:
Journal of Signal Processing Systems Aims and scope Submit manuscript

Abstract

We consider the problem of simultaneous sparse coding and anomaly detection in a collection of data vectors. The majority of the data vectors are assumed to conform with a sparse representation model, whereas the anomaly is caused by an unknown subset of the data vectors—the outliers—which significantly deviate from this model. The proposed approach utilizes the Alternating Direction Method of Multipliers (ADMM) to recover simultaneously the sparse representations and the outliers components for the entire collection. This approach provides a unified solution both for jointly sparse and independently sparse data vectors. We demonstrate the usefulness of the proposed approach for irregular heartbeats detection in Electrocardiogram (ECG) as well as for specular reflectance and shadows removal from natural images.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3
Figure 4
Figure 5
Figure 6
Figure 7
Figure 8

Similar content being viewed by others

Notes

  1. The observant reader may notice that problem (5) is actually separable, implying that we can solve for each column of X independently from the others. Nevertheless, we choose in this paper a joint solver for two reasons: (i) Giving a unified view of the two problems (5 and 6); and (ii) Our approach loses nothing in terms of complexity nor elegance when compared to the independent sparse coding tasks.

  2. Note that the related problem of a sparsely represented interference matrix E=ΨC, where Ψ is a dictionary and C is sparse, can be formulated as follows:

    $$\begin{array}{*{20}l} \min\limits_{\mathbf{X},\mathbf{C}} \frac{1}{2}\|\mathbf{Y}-\mathbf{D} \mathbf{X}-{\Psi} \mathbf{C}\|_{F}^{2}+ \alpha\|\mathbf{X}\|_{1,p} + \beta\|\mathbf{C}\|_{1,1} , \end{array} $$

    and its solution can be also obtained using the proposed approach in this section.

  3. Note that problem (7) is convex, therefore ADMM will approach the global minimum. Since the Frobenius-norm term in (7) is not separable, perfect convergence is not guaranteed, however, it was verified experimentally that the solution obtained by ADMM is sufficiently accurate after 50 iterations.

  4. All the results in this paper are reproducible with a MATLAB package that is freely available for distribution.

  5. http://www.physionet.org/physiobank/database/html/mitdbdir/records.htm

  6. A total of six dictionaries were trained—each using all of the dimensionality-reduced samples from each segment.

  7. This is in contrast to cast-shadows, where one part of an object is shadowed by another part.

References

  1. Chandola, V., Banerjee, A., Kumar, V. (2009). Anomaly detection: a survey. ACM Computing Surveys, 41(3), 15:1–15:58.

  2. Bruckstein, A.M., Donoho, D., Elad, M. (2009). From sparse solutions of systems of equations to sparse modeling of signals and images. Society for Industrial and Applied Mathematics Review, 51(1), 34–81.

  3. Nguyen, N.H., Nasrabadi, N.M., Tran, T.D. (2011). Robust multi-sensor classification via joint sparse representation. In International conference on information fusion (FUSION).

  4. Shekhar, S., Patel, V.M., Nasrabadi, M., Chellappa, R. (2012). Joint sparsity-based robust multimodal biometrics recognition. In The 12th European conference on computer vision (ECCV).

  5. Cong, Y., Yuan, J., Liu, J. (2011). Sparse reconstruction cost for abnormal event detection. In Computer vision and pattern recognition (CVPR).

  6. Zhao, B., Fei-Fei, L., Xing, E.P. (2011). Online detection of unusual events in videos via dynamic sparse coding. In Computer vision and pattern recognition (CVPR).

  7. Levorato, M., & Mitra, U. (2012). Fast anomaly detection in smartgrids via sparse approximation theory. In Sensor array and multichannel signal processing workshop (SAM).

  8. Cotter, S.F., Rao, B.D., Engan, K., Kreutz-Delgado, K. (2005). Sparse solutions to linear inverse problems with multiple measurement vectors. IEEE Transactions on Signal Processing, 53(7), 2477–2488.

  9. Kong, D., Ding, C., Huang, H. (2011). Robust nonnegative matrix factorization using l21-norm. In The 20th ACM international conference on information and knowledge management(CIKM).

  10. Dobigeon, N., & Févotte, C. (2013). Robust nonnegative matrix factorization for nonlinear unmixing of hyperspectral images. In The 5th workshop on hyperspectral image and signal processing: evolution in remote sensing (WHISPERS).

  11. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J. (2010). Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1), 1–122.

  12. Ince, T., Kiranyaz, S., Gabbouj, M. (2009). A generic and robust system for automated patient-specific classification of ecg signals. IEEE Transactions on Biomedical Engineering, 56(5), 1415–1426.

  13. Ye, C., Kumar, B.V., Coimbra, M.T. (2012). Heartbeat classification using morphological and dynamic features of ecg signals. IEEE Transactions on Biomedical Engineering, 59(10), 2930–2941.

  14. Mailhe, B., Gribonval, R., Bimbot, F., Lemay, M., Vandergheynst, P., Vesin, J. M. (2009). Dictionary learning for the sparse modelling of atrial fibrillation in ecg signals. In Internatioanl conference on acoustics, speech and signal processing (ICASSP).

  15. Moody, G.B., & Mark, R.G. (2001). The impact of the mit-bih arrhythmia database. IEEE Engineering in Medicine and Biology Magazine, 20(3), 45–50.

  16. Aharon, M., Elad, M., Bruckstein, A.M. (2006). K-svd: an algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11), 4311–4322.

  17. Beck, A., & Teboulle, M. (2009). A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Image Science.

  18. Szeliski, R. (2010). Computer vision: algorithms and applications. New York: Springer.

  19. Artusi, A., Banterle, F., Chetverikov, D. (2011). A survey of specularity removal methods. Computer Graphics Forum, 30(11).

  20. Basri, R., & Jacobs, D.W. (2003). Lambertian reflectance and linear subspaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(2).

  21. Shashua, A. (1997). On photometric issues in 3d visual recognition from a single 2d image. International Journal of Computer Vision, 21(1–2).

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Technion, Haifa, Israel

    Amir Adler, Michael Elad & Ehud Rivlin

  2. Computer Science Department, Interdisciplinary Center, Herzelia, Israel

    Yacov Hel-Or

Authors
  1. Amir Adler
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Elad
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yacov Hel-Or
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ehud Rivlin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Amir Adler.

Additional information

A. Adler is the recipient of the 2011 Google European Doctoral Fellowship in Multimedia, and this research is partly supported by this Google Fellowship and partly by ERC Grant agreement no. 320649.

Appendix

Appendix

The update equation for X k+1 is obtained by solving:

$$\begin{array}{*{20}l} \min\limits_{\mathbf{X}} &\frac{1}{2} \left\| \mathbf{Y}-\mathbf{D} \mathbf{X}-\mathbf{E}^{k} \right\|^{2}_{F} + <\mathbf{M}^{k},\mathbf{Z}^{k}-\mathbf{X}> + \frac{\mu^{k}}{2}\left\|\mathbf{Z}^{k}-\mathbf{X}\right\|^{2}_{F}. \end{array} $$
(29)

The solution of Eq. (29) is computed from:

$$\begin{array}{@{}rcl@{}} &&{}\frac{\partial}{\partial\mathbf{X}} \left(\frac{1}{2}\textbf{Tr}\left\{\left(\mathbf{Y}-\mathbf{D} \mathbf{X}-\mathbf{E}^{k}\right)\left(\mathbf{Y}-\mathbf{D} \mathbf{X}-\mathbf{E}^{k}\right)^{T}\right\}+ \textbf{Tr}\left\{(\mathbf{Z}^{k}-\mathbf{X})^{T} \mathbf{M}^{k}\right\} \right.\\ &&{\kern1.5pc}\left. + \frac{\mu^{k}}{2} \textbf{Tr}\left\{\left(\mathbf{Z}^{k}-\mathbf{X}\right)\left(\mathbf{Z}^{k}-\mathbf{X}\right)^{T}\right\}\right)=0, \end{array} $$
(30)

which results in:

$$\begin{array}{*{20}l} & \mathbf{D}^{T}\left(\mathbf{Y}-\mathbf{D} \mathbf{X}-\mathbf{E}^{k}\right) + \mathbf{M}^{k} + \mu^{k}\left(\mathbf{Z}^{k}-\mathbf{X}\right)=0, \end{array} $$
(31)

and the update equation is given by:

$$\begin{array}{*{20}l} \mathbf{X}^{k+1} = \left(\mathbf{D}^{T}\mathbf{D}+\mu^{k}\mathbf{I}\right)^{-1}\left(\mathbf{D}^{T}\left(\mathbf{Y}-\mathbf{E}^{k}\right) +\mathbf{M}^{k}+\mu^{k} \mathbf{Z}^{k}\right). \end{array} $$
(32)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Adler, A., Elad, M., Hel-Or, Y. et al. Sparse Coding with Anomaly Detection. J Sign Process Syst 79, 179–188 (2015). https://doi.org/10.1007/s11265-014-0913-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11265-014-0913-0

Keywords

Search

Navigation