Restatement - Share-based Compensation (Details) (USD $)	3 Months Ended		6 Months Ended
	Aug. 03, 2013	Jul. 28, 2012	Aug. 03, 2013	Jul. 28, 2012	Feb. 02, 2013
Consolidated Balance Sheet (unaudited)
Merchandise inventories	$ 909,000,000	$ 925,000,000	$ 909,000,000	$ 925,000,000	$ 862,000,000
Deferred income taxes	38,000,000	42,000,000	38,000,000	42,000,000	37,000,000
Income tax receivable	36,000,000	27,000,000	36,000,000	27,000,000	3,000,000
Total current assets	1,130,000,000	1,196,000,000	1,130,000,000	1,196,000,000	1,044,000,000
Deferred income taxes	29,000,000	32,000,000	29,000,000	32,000,000	30,000,000
Total non-current assets	168,000,000	181,000,000	168,000,000	181,000,000	173,000,000
Accrued liabilities and other	335,000,000	353,000,000	335,000,000	353,000,000	367,000,000
Share-based compensation liability	19,000,000	29,000,000	19,000,000	29,000,000	35,000,000
Income taxes payable					37,000,000
Total current liabilities	885,000,000	661,000,000	885,000,000	661,000,000	856,000,000
Share-based compensation liability	26,000,000	23,000,000	26,000,000	23,000,000	27,000,000
Total long-term liabilities	2,991,000,000	3,483,000,000	2,991,000,000	3,483,000,000	3,003,000,000
Additional paid-in capital	61,000,000	52,000,000	61,000,000	52,000,000	49,000,000
Accumulated deficit	(2,296,000,000)	(2,499,000,000)	(2,296,000,000)	(2,499,000,000)	(2,359,000,000)
Total stockholders' deficit	(2,231,000,000)	(2,441,000,000)	(2,231,000,000)	(2,441,000,000)	(2,304,000,000)
Consolidated Statements of Comprehensive Income (unaudited)
Cost of sales and occupancy expense	567,000,000	557,000,000	1,151,000,000	1,124,000,000
Gross Profit	337,000,000	335,000,000	746,000,000	746,000,000
Selling, general, and administrative expense	254,000,000	251,000,000	526,000,000	510,000,000
Share-based compensation	8,000,000	3,000,000	11,000,000	7,000,000
Operating income	71,000,000	76,000,000	199,000,000	220,000,000
Income before income taxes	25,000,000	15,000,000	99,000,000	94,000,000
Provision for income taxes	8,000,000	6,000,000	36,000,000	34,000,000
Net income	17,000,000	9,000,000	63,000,000	60,000,000
Comprehensive income	16,000,000	7,000,000	61,000,000	60,000,000
Operating activities:
Net income	17,000,000	9,000,000	63,000,000	60,000,000
Share-based compensation			13,000,000	11,000,000
Merchandise inventories			(47,000,000)	(82,000,000)
Accrued liabilities and other			(59,000,000)	(42,000,000)
Income taxes			(71,000,000)	(46,000,000)
Net cash provided by (used in) operating activities			(14,000,000)	(80,000,000)
Net cash provided by financing activities			59,000,000	(133,000,000)
As Reported
Consolidated Balance Sheet (unaudited)
Merchandise inventories	905,000,000	922,000,000	905,000,000	922,000,000
Deferred income taxes	37,000,000		37,000,000
Income tax receivable	34,000,000		34,000,000
Total current assets	1,123,000,000	1,193,000,000	1,123,000,000	1,193,000,000
Deferred income taxes	13,000,000	18,000,000	13,000,000	18,000,000
Total non-current assets	152,000,000	167,000,000	152,000,000	167,000,000
Accrued liabilities and other	338,000,000	351,000,000	338,000,000	351,000,000
Income taxes payable	1,000,000	2,000,000	1,000,000	2,000,000
Total current liabilities	870,000,000	632,000,000	870,000,000	632,000,000
Total long-term liabilities	2,965,000,000	3,460,000,000	2,965,000,000	3,460,000,000
Additional paid-in capital	60,000,000	62,000,000	60,000,000	62,000,000
Accumulated deficit	(2,277,000,000)	(2,474,000,000)	(2,277,000,000)	(2,474,000,000)
Total stockholders' deficit	(2,213,000,000)	(2,406,000,000)	(2,213,000,000)	(2,406,000,000)
Consolidated Statements of Comprehensive Income (unaudited)
Cost of sales and occupancy expense	567,000,000	553,000,000	1,153,000,000	1,119,000,000
Gross Profit	337,000,000	339,000,000	744,000,000	751,000,000
Selling, general, and administrative expense	258,000,000	252,000,000	529,000,000	512,000,000
Operating income	75,000,000	82,000,000	205,000,000	230,000,000
Income before income taxes	29,000,000	21,000,000	105,000,000	104,000,000
Provision for income taxes	9,000,000	8,000,000	38,000,000	38,000,000
Net income	20,000,000	13,000,000	67,000,000	66,000,000
Comprehensive income	19,000,000	11,000,000	65,000,000	66,000,000
Operating activities:
Net income	20,000,000	13,000,000	67,000,000	66,000,000
Share-based compensation			1,000,000	3,000,000
Merchandise inventories			(40,000,000)	(82,000,000)
Accrued liabilities and other			(38,000,000)
Income taxes			(71,000,000)	(43,000,000)
Net cash provided by (used in) operating activities			6,000,000	(79,000,000)
Repurchase of common stock			(45,000,000)	(3,000,000)
Proceeds from stock options exercised			25,000,000	2,000,000
Net cash provided by financing activities			39,000,000	(134,000,000)
Restatement Adjustment
Consolidated Statements of Comprehensive Income (unaudited)
Net income	(3,000,000)	(4,000,000)	(4,000,000)	(6,000,000)
Operating activities:
Net income	(3,000,000)	(4,000,000)	(4,000,000)	(6,000,000)
Restatement Adjustment | Share-based compensation Adjustment
Consolidated Balance Sheet (unaudited)
Merchandise inventories	4,000,000	3,000,000	4,000,000	3,000,000
Deferred income taxes	1,000,000		1,000,000
Income tax receivable	2,000,000		2,000,000
Total current assets	7,000,000	3,000,000	7,000,000	3,000,000
Deferred income taxes	16,000,000	14,000,000	16,000,000	14,000,000
Total non-current assets	16,000,000	14,000,000	16,000,000	14,000,000
Accrued liabilities and other	(3,000,000)	2,000,000	(3,000,000)	2,000,000
Share-based compensation liability	19,000,000	29,000,000	19,000,000	29,000,000
Income taxes payable	(1,000,000)	(2,000,000)	(1,000,000)	(2,000,000)
Total current liabilities	15,000,000	29,000,000	15,000,000	29,000,000
Share-based compensation liability	26,000,000	23,000,000	26,000,000	23,000,000
Total long-term liabilities	26,000,000	23,000,000	26,000,000	23,000,000
Additional paid-in capital	1,000,000	(10,000,000)	1,000,000	(10,000,000)
Accumulated deficit	(19,000,000)	(25,000,000)	(19,000,000)	(25,000,000)
Total stockholders' deficit	(18,000,000)	(35,000,000)	(18,000,000)	(35,000,000)
Consolidated Statements of Comprehensive Income (unaudited)
Cost of sales and occupancy expense	1,000,000	4,000,000	2,000,000	4,000,000
Gross Profit	(1,000,000)	(4,000,000)	(2,000,000)	(4,000,000)
Selling, general, and administrative expense	(2,000,000)	(1,000,000)	(1,000,000)	(2,000,000)
Share-based compensation	8,000,000	3,000,000	11,000,000	7,000,000
Operating income	(7,000,000)	(6,000,000)	(12,000,000)	(9,000,000)
Income before income taxes	(7,000,000)	(6,000,000)	(12,000,000)	(9,000,000)
Provision for income taxes	(2,000,000)	(2,000,000)	(4,000,000)	(4,000,000)
Net income	(5,000,000)	(4,000,000)	(8,000,000)	(5,000,000)
Comprehensive income	(5,000,000)	(4,000,000)	(8,000,000)	(5,000,000)
Operating activities:
Net income	(5,000,000)	(4,000,000)	(8,000,000)	(5,000,000)
Share-based compensation			12,000,000	8,000,000
Merchandise inventories			(2,000,000)	(1,000,000)
Accrued liabilities and other			(21,000,000)
Income taxes			(2,000,000)	(3,000,000)
Net cash provided by (used in) operating activities			(20,000,000)	(1,000,000)
Repurchase of common stock			45,000,000	3,000,000
Proceeds from stock options exercised			(25,000,000)	(2,000,000)
Net cash provided by financing activities			20,000,000	1,000,000
Restatement Adjustment | Other Adjustments
Consolidated Statements of Comprehensive Income (unaudited)
Cost of sales and occupancy expense	(1,000,000)		(4,000,000)	1,000,000
Gross Profit	1,000,000		4,000,000	(1,000,000)
Selling, general, and administrative expense	(2,000,000)		(2,000,000)
Operating income	3,000,000		6,000,000	(1,000,000)
Income before income taxes	3,000,000		6,000,000	(1,000,000)
Provision for income taxes	(1,000,000)		2,000,000
Net income	2,000,000		4,000,000	(1,000,000)
Comprehensive income	2,000,000		4,000,000	(1,000,000)
Operating activities:
Net income	2,000,000		4,000,000	(1,000,000)
Merchandise inventories			(5,000,000)	1,000,000
Income taxes			$ 2,000,000