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

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.

Inspec keywords: signal reconstruction; convergence; gradient methods; stochastic programming; minimisation

Other keywords: heavy column outliers corruption; adaptive stochastic gradient algorithm; geodesic; extended Yale face dataset; stochastic gradient method; large matrix; low-rank subspace; L2-1 norm minimisation; convergence rate; gradient step; synthetic data; GASG21; Grassmannian adaptive stochastic gradient; stochastic programming counterpart

Subjects: Signal processing theory; Signal processing and detection; Optimisation techniques; Optimisation techniques; Interpolation and function approximation (numerical analysis); Interpolation and function approximation (numerical analysis)

References

    1. 1)
      • 17. He, J., Balzano, L., Lui, J.: ‘Online robust subspace tracking from partial information’, Arxiv preprint arXiv:1109.3827, 2011.
    2. 2)
      • 28. Plakhov, A., Cruz, P.: ‘A stochastic approximation algorithm with step-size adaptation’, J. Math. Sci., 2004, 120, (1), pp. 964973.
    3. 3)
      • 14. Candès, E.J., Li, X., Ma, Y., et al: ‘Robust principal component analysis?’, J. ACM, 2011, 58, (3), pp. 137.
    4. 4)
      • 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.
    5. 5)
      • 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.
    6. 6)
      • 15. Mateos, G., Giannakis, G.B.: ‘Robust PCA as bilinear decomposition with outlier-sparsity regularization’, IEEE Trans. Signal Process., 2012, 60, (10), pp. 51765190.
    7. 7)
      • 37. Ngo, T., Saad, Y.: ‘Scaled gradients on Grassmann manifolds for matrix completion’. Advances in Neural Information Processing Systems, 2012, pp. 14121420.
    8. 8)
      • 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.
    9. 9)
      • 13. Hsu, D., Kakade, S.M., Zhang, T.: ‘Robust matrix decomposition with sparse corruptions’, IEEE Trans. Inf. Theory, 2011, 57, (11), pp. 72217234.
    10. 10)
      • 27. Kushner, H.J., Yin, G.: ‘Stochastic approximation and recursive algorithms and applications’ (Springer Science & Business Media, 2003), vol. 35.
    11. 11)
      • 30. Nedić, A., Bertsekas, D.: ‘Convergence rate of incremental subgradient algorithms’. Stochastic Optimization: Algorithms and Applications, 2001, pp. 223264.
    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)
      • 33. Sanderson, C.: ‘Armadillo: an open source C++ linear algebra library for fast prototyping and computationally intensive experiments’. Technical Report, 2010.
    14. 14)
      • 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.
    15. 15)
      • 21. Feng, J., Xu, H., Mannor, S., et al: ‘Online pca for contaminated data’. Advances in Neural Information Processing Systems, 2013, pp. 764772.
    16. 16)
      • 7. Xu, H., Caramanis, C., Mannor, S.: ‘Outlier-robust PCA: the high dimensional case’, IEEE Trans. Inf. Theory, 2013, 59, (1), pp. 546572.
    17. 17)
      • 26. Robbins, H., Monro, S.: ‘A stochastic approximation method’. The Annals of Mathematical Statistics, 1951, pp. 400407.
    18. 18)
      • 31. Zhang, D., Balzano, L.: ‘Global convergence of a grassmannian gradient descent algorithm for subspace estimation’, arXiv preprint arXiv:1506.07405, 2015.
    19. 19)
      • 32. Balzano, L., Wright, S.: ‘Local convergence of an algorithm for subspace identification from partial data’, Found. Comput. Math., 2015, 15, (5), pp. 12791314.
    20. 20)
      • 6. Xu, H., Caramanis, C., Sanghavi, S.: ‘Robust PCA via outlier pursuit’, IEEE Trans. Inf. Theory, 2012, 58, (5), pp. 30473064.
    21. 21)
      • 10. Chandrasekaran, V., Sanghavi, S., Parrilo, P., et al: ‘Rank-sparsity incoherence for matrix decomposition’, SIAM J. Optim., 2011, 21, (2), pp. 572596.
    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)
      • 38. Mishra, H.B., Adithya Apuroop, K., Sepulchre, R.: ‘A Riemannian geometry for low-rank matrix completion’, arXiv preprint arXiv:1211.1550, 2012.
    24. 24)
      • 4. Basri, R., Jacobs, D.: ‘Lambertian reflectance and linear subspaces’, IEEE Trans. Pattern Anal. Mach. Intell., 2003, 25, (2), pp. 218233.
    25. 25)
      • 5. Huber, P.J., Ronchetti, E.M.: ‘Robust statistics’ (Wiley, 2009).
    26. 26)
      • 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.
    27. 27)
      • 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.
    28. 28)
      • 16. Li, Y.: ‘On Incremental and robust subspace learning’, Pattern Recogn., 2004, 37, (7), pp. 15091518.
    29. 29)
      • 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.
    30. 30)
      • 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.
    31. 31)
      • 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.
    32. 32)
      • 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.
    33. 33)
      • 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.
    34. 34)
      • 20. Feng, J., Xu, H., Yan, S.: ‘Online robust PCA via stochastic optimization’. Advances in Neural Information Processing Systems, 2013, pp. 404412.
    35. 35)
      • 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.
    36. 36)
      • 9. Zhang, T., Lerman, G.: ‘A novel m-estimator for robust pca’, J. Mach. Learn. Res., 2014, 15, (1), pp. 749808.
    37. 37)
      • 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.
    38. 38)
      • 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.
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