http://iet.metastore.ingenta.com
1887

Adaptive stochastic gradient descent on the Grassmannian for robust low-rank subspace recovery

Adaptive stochastic gradient descent on the Grassmannian for robust low-rank subspace recovery

For access to this article, please select a purchase option:

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Signal Processing — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this study, the authors present GASG21 (Grassmannian adaptive stochastic gradient for L 2,1 norm minimisation), an adaptive stochastic gradient algorithm to robustly recover the low-rank subspace from a large matrix. In the presence of column outliers corruption, the authors reformulate the classical matrix L 2,1 norm minimisation problem as its stochastic programming counterpart. For each observed data vector, the low-rank subspace is updated by taking a gradient step along the geodesic of Grassmannian. In order to accelerate the convergence rate of the stochastic gradient method, the authors choose to adaptively tune the constant step-size by leveraging the consecutive gradients. Numerical experiments on synthetic data and the extended Yale face dataset demonstrate the efficiency and accuracy of the proposed GASG21 algorithm even with heavy column outliers corruption.

References

    1. 1)
      • 1. Moulines, E., Duhamel, P., Cardoso, J.F., et al: ‘Subspace methods for the blind identification of multichannel FIR filters’, IEEE Trans. Signal Process., 1995, 43, (5), pp. 516525.
    2. 2)
      • 2. Krim, S.H., Viberg, M.: ‘Two decades of array signal processing research: the parametric approach’, IEEE Signal Process. Mag., 1996, 13, (4), pp. 6794.
    3. 3)
      • 3. Audette, M.A., Ferrie, F.P., Peters, T.M.: ‘An algorithmic overview of surface registration techniques for medical imaging’, Med. Image Anal., 2000, 4, (3), pp. 201217.
    4. 4)
      • 4. Basri, R., Jacobs, D.: ‘Lambertian reflectance and linear subspaces’, IEEE Trans. Pattern Anal. Mach. Intell., 2003, 25, (2), pp. 218233.
    5. 5)
      • 5. Huber, P.J., Ronchetti, E.M.: ‘Robust statistics’ (Wiley, 2009).
    6. 6)
      • 6. Xu, H., Caramanis, C., Sanghavi, S.: ‘Robust PCA via outlier pursuit’, IEEE Trans. Inf. Theory, 2012, 58, (5), pp. 30473064.
    7. 7)
      • 7. Xu, H., Caramanis, C., Mannor, S.: ‘Outlier-robust PCA: the high dimensional case’, IEEE Trans. Inf. Theory, 2013, 59, (1), pp. 546572.
    8. 8)
      • 8. Lerman, G., McCoy, M., Tropp, J.A., et al: ‘Robust computation of linear models by convex relaxation’, Found. Comput. Math., 2015, 15, (2), pp. 363410.
    9. 9)
      • 9. Zhang, T., Lerman, G.: ‘A novel m-estimator for robust pca’, J. Mach. Learn. Res., 2014, 15, (1), pp. 749808.
    10. 10)
      • 10. Chandrasekaran, V., Sanghavi, S., Parrilo, P., et al: ‘Rank-sparsity incoherence for matrix decomposition’, SIAM J. Optim., 2011, 21, (2), pp. 572596.
    11. 11)
      • 11. Wright, J., Ganesh, A., Rao, S., et al: ‘Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization’. Advances in Neural Information Processing Systems, 2009, pp. 20802088.
    12. 12)
      • 12. Agarwal, A., Negahban, S., Wainwright, M.J.: ‘Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions’, Ann. Stat., 2012, 40, (2), pp. 11711197.
    13. 13)
      • 13. Hsu, D., Kakade, S.M., Zhang, T.: ‘Robust matrix decomposition with sparse corruptions’, IEEE Trans. Inf. Theory, 2011, 57, (11), pp. 72217234.
    14. 14)
      • 14. Candès, E.J., Li, X., Ma, Y., et al: ‘Robust principal component analysis?’, J. ACM, 2011, 58, (3), pp. 137.
    15. 15)
      • 15. Mateos, G., Giannakis, G.B.: ‘Robust PCA as bilinear decomposition with outlier-sparsity regularization’, IEEE Trans. Signal Process., 2012, 60, (10), pp. 51765190.
    16. 16)
      • 16. Li, Y.: ‘On Incremental and robust subspace learning’, Pattern Recogn., 2004, 37, (7), pp. 15091518.
    17. 17)
      • 17. He, J., Balzano, L., Lui, J.: ‘Online robust subspace tracking from partial information’, Arxiv preprint arXiv:1109.3827, 2011.
    18. 18)
      • 18. He, J., Balzano, L., Szlam, A.: ‘Incremental gradient on the grassmannian for online foreground and background separation in subsampled video’. 2012 IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 15681575.
    19. 19)
      • 19. Guo, H., Qiu, C., Vaswani, N.: ‘An online algorithm for separating sparse and low-dimensional signal sequences from their sum’, IEEE Trans. Signal Process., 2014, 62, (16), pp. 42844297.
    20. 20)
      • 20. Feng, J., Xu, H., Yan, S.: ‘Online robust PCA via stochastic optimization’. Advances in Neural Information Processing Systems, 2013, pp. 404412.
    21. 21)
      • 21. Feng, J., Xu, H., Mannor, S., et al: ‘Online pca for contaminated data’. Advances in Neural Information Processing Systems, 2013, pp. 764772.
    22. 22)
      • 22. Goes, J., Zhang, T., Arora, R., et al: ‘Robust stochastic principal component analysis’. Proc. of the Seventeenth Int. Conf. on Artificial Intelligence and Statistics, 2014, pp. 266274.
    23. 23)
      • 23. Balzano, L., Nowak, R., Recht, B.: ‘Online identification and tracking of subspaces from highly incomplete information’. 2010 48th Annual Allerton Conf. on Communication, Control, and Computing (Allerton), pp. 704711.
    24. 24)
      • 24. Cevher, V., Becker, S., Schmidt, M.: ‘Convex optimization for big data: scalable, randomized, and parallel algorithms for big data analytics’, IEEE Signal Process. Mag., 2014, 31, (5), pp. 3243.
    25. 25)
      • 25. Edelman, A., Arias, T.A., Smith, S.T.: ‘The geometry of algorithms with orthogonality constraints’, SIAM J. Matrix Anal. Appl., 1998, 20, (2), pp. 303353.
    26. 26)
      • 26. Robbins, H., Monro, S.: ‘A stochastic approximation method’. The Annals of Mathematical Statistics, 1951, pp. 400407.
    27. 27)
      • 27. Kushner, H.J., Yin, G.: ‘Stochastic approximation and recursive algorithms and applications’ (Springer Science & Business Media, 2003), vol. 35.
    28. 28)
      • 28. Plakhov, A., Cruz, P.: ‘A stochastic approximation algorithm with step-size adaptation’, J. Math. Sci., 2004, 120, (1), pp. 964973.
    29. 29)
      • 29. Klein, S., Pluim, J., Staring, M., et al: ‘Adaptive stochastic gradient descent optimisation for image registration’, Int. J. Comput. Vis., 2009, 81, (3), pp. 227239.
    30. 30)
      • 30. Nedić, A., Bertsekas, D.: ‘Convergence rate of incremental subgradient algorithms’. Stochastic Optimization: Algorithms and Applications, 2001, pp. 223264.
    31. 31)
      • 31. Zhang, D., Balzano, L.: ‘Global convergence of a grassmannian gradient descent algorithm for subspace estimation’, arXiv preprint arXiv:1506.07405, 2015.
    32. 32)
      • 32. Balzano, L., Wright, S.: ‘Local convergence of an algorithm for subspace identification from partial data’, Found. Comput. Math., 2015, 15, (5), pp. 12791314.
    33. 33)
      • 33. Sanderson, C.: ‘Armadillo: an open source C++ linear algebra library for fast prototyping and computationally intensive experiments’. Technical Report, 2010.
    34. 34)
      • 34. Kennedy, R., Taylor, C.J., Balzano, L.: ‘Online completion of Ill-conditioned low-rank matrices’. IEEE Global Conf. on Signal and Information Processing (GlobalSIP), 2014.
    35. 35)
      • 35. Lee, K.C., Ho, J., Kriegman, D.: ‘Acquiring linear subspaces for face recognition under variable lighting’, IEEE Trans. Pattern Anal. Mach. Intell., 2005, 27, (5), pp. 684698.
    36. 36)
      • 36. Li, F.F., Fergus, R., Perona, P.: ‘Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories’, Comput. Vis. Image Underst., 2007, 106, (1), pp. 5970.
    37. 37)
      • 37. Ngo, T., Saad, Y.: ‘Scaled gradients on Grassmann manifolds for matrix completion’. Advances in Neural Information Processing Systems, 2012, pp. 14121420.
    38. 38)
      • 38. Mishra, H.B., Adithya Apuroop, K., Sepulchre, R.: ‘A Riemannian geometry for low-rank matrix completion’, arXiv preprint arXiv:1211.1550, 2012.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-spr.2016.0049
Loading

Related content

content/journals/10.1049/iet-spr.2016.0049
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address