Restructuring Program and Other Store Exit Costs -Accrued Liabilities for Restructuring (Details) - USD ($) $ in Thousands	9 Months Ended	12 Months Ended
	Jan. 31, 2015	Jan. 30, 2016	Jan. 31, 2015	Feb. 01, 2014
Restructuring Reserve [Roll Forward]
Additions		$ (6,100)	$ 40,356	$ 0
2014 Cost Reduction Program
Restructuring Reserve [Roll Forward]
Beginning Balance	$ 16,771	12,621
Additions	23,585	259
Paid or Utilized	(45,453)	(6,521)
Adjustments	17,718	(6,359)
Ending Balance	12,621	0	12,621
2014 Cost Reduction Program | Impairment charges
Restructuring Reserve [Roll Forward]
Beginning Balance	30,497	0
Additions	0
Paid or Utilized	(30,497)
Adjustments	0
Ending Balance	0		0
2014 Cost Reduction Program | Severance
Restructuring Reserve [Roll Forward]
Beginning Balance	1,060	28
Additions	3,054	0
Paid or Utilized	(4,086)	(28)
Adjustments	0	0
Ending Balance	28	0	28
2014 Cost Reduction Program | Lease Costs
Restructuring Reserve [Roll Forward]
Beginning Balance	1,046	12,593
Additions	18,355	0
Paid or Utilized	(6,808)	(6,234)
Adjustments	0	(6,359)
Ending Balance	12,593	0	12,593
2014 Cost Reduction Program | Unamortized Tenant Allowance and Deferred Rent
Restructuring Reserve [Roll Forward]
Beginning Balance	(17,718)	0
Additions	0
Adjustments	17,718
Ending Balance	0		0
2014 Cost Reduction Program | Other exit costs
Restructuring Reserve [Roll Forward]
Beginning Balance	1,886	0
Additions	2,176	259
Paid or Utilized	(4,062)	(259)
Adjustments	0	0
Ending Balance	$ 0	$ 0	$ 0